codeforces 145 E. Lucky Queries (线段树lazy标记)
题意：给出一串只由数字'4'和'7'组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的没个数反转，反转的定义为，4变成7,7变成4.
思路：线段树lazy标记。
线段树的域记录5个信息，c4,c7,c47,c74，flip,a分别表示4的个数,7的个数，非下降子序列的个数，非上升的子序列的个数，以及该区间是否被翻转。
纠结了很久PushUp操作。。。。
c4和c7倒是没什么疑问。。。。
一开始觉得c47是由三部分的最大值更新得到的。。。
left.c4+right.c47,left.c4+right.c7,left.c47+right.c7...
但是样例过不了。。。
纠结了半天发现。。。
比如4774,4444是左右两个区间的时候。。。。
c47最大是5.。。但是left.c4 + right.c7=6，比正确答案大。
原因是。。一个区间中4的位置可能是分散的。。。这样只有某段连续出现的4对答案的贡献是正确的。。。
所以只有区间长度为1的时候c4+c7的更新方式才是合法的。。。
我们不妨在初始化的时候。。。。在线段树的叶子节点直接设置c47为1（当然相应地c74也要为1）
另外一个收获是。。。线段树对于区间的操作（对于点的操作也是同样）
不一定是某种常见的定义过的操作（求和啊，最大值最小值啊之类的）
也可能是某种自定义的操作。。。
比如这道题中的flip操作。。。
就是对区间的一个自定义的操作。。。
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 27 Sep 2016 09:14:22 AM CST
4File Name :code/cf/problem/145E.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N = 1E6+7;
32int n,m;
33char st[N];
34struct node
35{
36 int c7,c4,c47,c74;
37 bool flip;
38 void out()
39 {
40 printf("c4:%d c7: %d c47 :%d c74 : %d\n",c4,c7,c47,c74);
41 }
42}tree[N<<2];
43void PushUp( int rt)
44{
45 tree[rt].c4 = tree[rt<<1].c4 + tree[rt<<1|1].c4;
46 tree[rt].c7 = tree[rt<<1].c7 + tree[rt<<1|1].c7;
47 tree[rt].c47 = max(tree[rt<<1].c4 + tree[rt<<1|1].c47 , tree[rt<<1].c47 + tree[rt<<1|1].c7);
48 tree[rt].c74 = max(tree[rt<<1].c7 + tree[rt<<1|1].c74, tree[rt<<1].c74 + tree[rt<<1|1].c4);
49}
50void build( int l,int r ,int rt)
51{
52 if (l==r)
53 {
54 if (st[l-1]=='4') tree[rt].c4 = 1;
55 else tree[rt].c7 = 1;
56 tree[rt].c47 = tree[rt].c74 = 1;
57 return;
58 }
59 int m = (l+r)>>1;
60 build(lson);
61 build(rson);
62 PushUp(rt);
63}
64void Flip( int rt)
65{
66 tree[rt].flip^=1;
67 swap(tree[rt].c4,tree[rt].c7);
68 swap(tree[rt].c47,tree[rt].c74);
69}
70void PushDown( int rt)
71{
72 if (tree[rt].flip)
73 {
74 Flip(rt<<1);
75 Flip(rt<<1|1);
76 tree[rt].flip = 0 ;
77 }
78}
79void update(int L,int R,int l,int r,int rt)
80{
81 if (L<=l&&r<=R)
82 {
83 Flip(rt);
84 return;
85 }
86 PushDown(rt);
87 int m = (l+r)>>1;
88 if (L<=m) update(L,R,lson);
89 if (R>=m+1) update(L,R,rson);
90 PushUp(rt);
91}
92int main()
93{
94#ifndef ONLINE_JUDGE
95 freopen("code/in.txt","r",stdin);
96#endif
97 scanf("%d%d",&n,&m);
98 scanf("%s",st);
99 build(1,n,1);
100 while (m--)
101 {
102 char opt[10];
103 scanf("%s",opt);
104 // cout<<"opt:"<<opt<<endl;
105 if (opt[0]=='c')
106 {
107 printf("%d\n",tree[1].c47);
108 }
109 else
110 {
111 int x,y;
112 scanf("%d%d",&x,&y);
113 update(x,y,1,n,1);
114 }
115 }
116#ifndef ONLINE_JUDGE
117 fclose(stdin);
118#endif
119 return 0;
120}