P2253 好一个一中腰鼓 --线段树
题目背景
话说我大一中的运动会就要来了，据本班同学剧透（其实早就知道了），我萌萌的初二年将要表演腰鼓[喷]，这个无厘头的题目便由此而来。
Ivan乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外人间隔。”
题目描述
设想一下，腰鼓有两面，一面是红色的，一面是白色的。初二的苏大学神想给你这个oier出一道题。假设一共有N（1<=N<=20,000）个同学表演，表演刚开始每一个鼓都是红色面朝向观众，舞蹈老师会发出M（1<=M<=20,000）个指令，如果指令发给第i个表演的同学,这位同学就会把腰鼓反过来，如果腰鼓之前是红色面朝向观众的,那么就会变成白色面朝向观众，反之亦然。那么问题来了（！？），在老师每一次发出指令后，找到最长的连续的一排同学，满足每相邻的两个手中的腰鼓朝向观众的一面互不相同，输出这样一排连续的同学的人数。
输入输出格式
输入格式：
第一行有两个整数, 分别为表演的同学总数N, 和指令总数M。
之后M行, 每行有一个整数i: 1<=i<=N, 表示舞蹈老师发出的指令。
输出格式：
输出有M行, 其中每i行有一个整数.
表示老师的第i条指令发出之后, 可以找到的满足要求的最长连续的一排表演同学有多长?
输入输出样例
输入样例#1：
6 2 2 4
输出样例#1：
3 5
说明
Huangc温馨提示：其实数据根本没你想象的那么大。。。[坏笑]、、
1 /* 2 在区间维护三个值 3 一个是le 代表从左端点开始向右的最大01序列 4 一个是ri 代表从右端点开始向左的最大01序列 5 一个是all 代表整个区间最大的01序列 6 xl 代表区间左端点的值 7 xr 代表区间右端点的值 8 */ 9 #include <cstdio> 10 #include <ctype.h> 11 12 const int MAXN=20010; 13 14 int n,m; 15 16 struct node { 17 int l,r; 18 int xl,xr; 19 int le,ri,all; 20 }; 21 node t[MAXN<<2]; 22 23 inline void read(int&x) { 24 int f=1;register char c=getchar(); 25 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 26 for(;isdigit(c);x=x*10+c-48,c=getchar()); 27 x=x*f; 28 } 29 30 inline int max(int a,int b) { 31 return a<b?b:a; 32 } 33 34 inline void up(int now) { 35 t[now].xl=t[now<<1].xl;t[now].xr=t[now<<1|1].xr; 36 t[now].le=t[now<<1].le;t[now].ri=t[now<<1|1].ri; 37 t[now].all=max(t[now<<1].all,max(t[now<<1|1].all,max(t[now<<1|1].le,t[now<<1].ri))); 38 if(t[now<<1].xr==t[now<<1|1].xl^1) { 39 t[now].all=max(t[now].all,t[now<<1].ri+t[now<<1|1].le); 40 if(t[now<<1].le==(t[now<<1].r-t[now<<1].l+1)) 41 t[now].le=max(t[now].le,t[now<<1].le+t[now<<1|1].le); 42 if(t[now<<1|1].ri==(t[now<<1|1].r-t[now<<1|1].l+1)) 43 t[now].ri=max(t[now].ri,t[now<<1|1].ri+t[now<<1].ri); 44 } 45 return; 46 } 47 48 void build_tree(int now,int l,int r) { 49 t[now].l=l,t[now].r=r; 50 if(l==r) { 51 t[now].xl=t[now].xr=1; 52 t[now].le=t[now].ri=t[now].all=1; 53 return; 54 } 55 int mid=(l+r)>>1; 56 build_tree(now<<1,l,mid); 57 build_tree(now<<1|1,mid+1,r); 58 up(now); 59 } 60 61 void modify(int now,int pos) { 62 if(t[now].l==t[now].r) { 63 t[now].xl=t[now].xr=t[now].xl^1; 64 return; 65 } 66 int mid=(t[now].l+t[now].r)>>1; 67 if(pos<=mid) modify(now<<1,pos); 68 else modify(now<<1|1,pos); 69 up(now); 70 } 71 72 int hh() { 73 int x; 74 read(n);read(m); 75 build_tree(1,1,n); 76 for(int i=1;i<=m;++i) { 77 read(x); 78 modify(1,x); 79 printf("%d ",t[1].all); 80 } 81 return 0; 82 } 83 84 int sb=hh(); 85 int main() {;}