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操作。。。
就是对区间的一个自定义的操作。。。
/* ***********************************************
Author :111qqz
Created Time :Tue 27 Sep 2016 09:14:22 AM CST
File Name :code/cf/problem/145E.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N = 1E6+7;
int n,m;
char st[N];
struct node
{
int c7,c4,c47,c74;
bool flip;
void out()
{
printf("c4:%d c7: %d c47 :%d c74 : %d\n",c4,c7,c47,c74);
}
}tree[N<<2];
void PushUp( int rt)
{
tree[rt].c4 = tree[rt<<1].c4 + tree[rt<<1|1].c4;
tree[rt].c7 = tree[rt<<1].c7 + tree[rt<<1|1].c7;
tree[rt].c47 = max(tree[rt<<1].c4 + tree[rt<<1|1].c47 , tree[rt<<1].c47 + tree[rt<<1|1].c7);
tree[rt].c74 = max(tree[rt<<1].c7 + tree[rt<<1|1].c74, tree[rt<<1].c74 + tree[rt<<1|1].c4);
}
void build( int l,int r ,int rt)
{
if (l==r)
{
if (st[l-1]=='4') tree[rt].c4 = 1;
else tree[rt].c7 = 1;
tree[rt].c47 = tree[rt].c74 = 1;
return;
}
int m = (l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
void Flip( int rt)
{
tree[rt].flip^=1;
swap(tree[rt].c4,tree[rt].c7);
swap(tree[rt].c47,tree[rt].c74);
}
void PushDown( int rt)
{
if (tree[rt].flip)
{
Flip(rt<<1);
Flip(rt<<1|1);
tree[rt].flip = 0 ;
}
}
void update(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
Flip(rt);
return;
}
PushDown(rt);
int m = (l+r)>>1;
if (L<=m) update(L,R,lson);
if (R>=m+1) update(L,R,rson);
PushUp(rt);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
scanf("%s",st);
build(1,n,1);
while (m--)
{
char opt[10];
scanf("%s",opt);
// cout<<"opt:"<<opt<<endl;
if (opt[0]=='c')
{
printf("%d\n",tree[1].c47);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
update(x,y,1,n,1);
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}