Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b）
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
10 10 0 0 0 1 1 0 1 0 1 1 1 0 2 3 0 5 2 2 2 4 0 4 0 3 6 2 3 7 4 2 8 1 0 5 0 5 6 3 3 9
Sample Output
5 2 6 5
HINT
对于30%的数据，1<=n, m<=1000 对于100%的数据，1<=n, m<=100000
题解
线段树裸题，但处理比较麻烦。 统计： fl[1]表示这个区间从左边开始连续1的个数， fr[2]是从区间右边开始。 利用这两个来维护maxl所表示的区间最长连续1。 setv表示将这个区间更新为多少。 change表示这个区间里的数是否取反。 其中还有几点注意：
区间维护时要保证setv和change最多只能存在一个。比如setv在更新时change就没有用了，重新将change改为0。对于change，不能用true和false来维护，因为一个区间可能会连续取反多次，所以每次给change++，当change为奇数时说明这个区间需要取反。一定要注意细节。 我的细节见代码。代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 100010#define lson o << 1#define rson o << 1 | 1struct tree{ int fl[2],fr[2]; int setv; int ch; // have changed? int sum[2],maxl[2];}t[N << 2];int ll,rr;void pushup(int o,int l,int r){ int mid = (l+r) >> 1; for(int i = 0;i < 2;i++) { t[o].fl[i] = t[lson].fl[i]+(t[lson].fl[i] == mid-l+1 ? t[rson].fl[i] : 0); t[o].fr[i] = t[rson].fr[i]+(t[rson].fr[i] == r-mid ? t[lson].fr[i] : 0); t[o].maxl[i] = max(max(t[lson].maxl[i],t[rson].maxl[i]),t[lson].fr[i]+t[rson].fl[i]); t[o].sum[i] = t[lson].sum[i] + t[rson].sum[i]; }}void init(int o,int x,int len){//ÓÃ×÷setµÄ¸üРt[o].maxl[x] = t[o].sum[x] = t[o].fl[x] = t[o].fr[x] = len; t[o].maxl[x^1] = t[o].sum[x^1] = t[o].fl[x^1] = t[o].fr[x^1] = 0;}void build(int o,int l,int r){ if(l == r) { int x; scanf("%d",&x); init(o,x,1); t[o].setv = -1; t[o].ch = 0; return; } int mid = (l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(o,l,r); t[o].setv = -1; t[o].ch = 0;}void SWAP(int o){//ÓÃ×÷changeµÄ¸üРswap(t[o].maxl[0],t[o].maxl[1]); swap(t[o].sum[0],t[o].sum[1]); swap(t[o].fl[0],t[o].fl[1]); swap(t[o].fr[0],t[o].fr[1]);}void pushdown(int o,int l,int r){ int mid = (l+r)>>1; if(t[o].ch % 2) { if(t[lson].setv != -1) { int x = t[lson].setv ^ 1; t[lson].setv = x; init(lson,x,mid-l+1); t[lson].ch = 0; }else{SWAP(lson); t[lson].ch++;} if(t[rson].setv != -1) { int x = t[rson].setv ^ 1; t[rson].setv = x; init(rson,x,r-mid); t[rson].ch = 0; }else{SWAP(rson); t[rson].ch++;} t[o].ch = false; } if(t[o].setv != -1 ) { int x = t[o].setv; t[lson].setv = t[rson].setv = x; init(lson,x,mid-l+1); init(rson,x,r-mid); t[lson].ch = t[rson].ch = 0; t[o].setv = -1; }}void update(int o,int l,int r,int d)//setv´æÔÚʱҪ±£Ö¤ch=false { if(ll <= l && rr >= r) { t[o].setv = d; t[o].ch = false; init(o,d,r-l+1); return; } pushdown(o,l,r); int mid = (l+r)>>1; if(ll <= mid) update(lson,l,mid,d); if(rr > mid) update(rson,mid+1,r,d); pushup(o,l,r);}void change(int o,int l,int r){ if(ll <= l && rr >= r) { if(t[o].setv != -1) { int d = t[o].setv ^ 1; t[o].setv = d; init(o,d,r-l+1); } else { t[o].ch++; SWAP(o); } return; } pushdown(o,l,r); int mid = (l+r)>>1; if(ll <= mid) change(lson,l,mid); if(rr > mid) change(rson,mid+1,r); pushup(o,l,r);}int querysum(int o,int l,int r){ if(ll <= l && rr >= r) return t[o].sum[1]; pushdown(o,l,r); int mid = (l+r)>>1,ans = 0; if(ll <= mid) ans += querysum(lson,l,mid); if(rr > mid) ans += querysum(rson,mid+1,r); //PRintf("(%d %d %d)",l,r,ans); return ans;}int querylen(int o,int l,int r){ if(ll <= l && rr >= r) return t[o].maxl[1]; pushdown(o,l,r); int mid = (l+r)>>1,ans = 0; if(ll <= mid) ans = max(ans,querylen(lson,l,mid)); if(rr > mid) ans = max(ans,querylen(rson,mid+1,r)); if(ll <= mid && rr > mid) ans = max(ans,min(mid-ll+1,t[lson].fr[1])+min(t[rson].fl[1],rr-mid)); return ans;}int main(){ int n,m,opt; scanf("%d%d",&n,&m); build(1,1,n); while(m--) { scanf("%d%d%d",&opt,&ll,&rr); ll++; rr++; if(opt <= 1) update(1,1,n,opt); else if(opt == 2) change(1,1,n); else if(opt == 3) printf("%d/n",querysum(1,1,n)); else printf("%d/n",querylen(1,1,n)); } return 0;}
