hdu3911Black And White (线段树，段异或，段查寻)
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>#include<iostream>#include<vector>using namespace std;#define N 100100struct edg{ int len;//最左，右的长度 char c;//颜色};struct nn{ int wlen,blen,need;//分别代表当前段的最长连续白色，黑色和子节点是否须要更新（1更新，0不用） struct edg LL,RR;//节点的最左边和最右边连续黑或白}tree[6*N];int max(int a,int b){return a>b?a:b;}//-------------异或-------------void sepw(int k){ int t; t=tree[k].blen; tree[k].blen=tree[k].wlen; tree[k].wlen=t; if(tree[k].LL.c=='w')tree[k].LL.c='b';else tree[k].LL.c='w'; if(tree[k].RR.c=='w')tree[k].RR.c='b';else tree[k].RR.c='w';}//----------根据子节点更新父节点k-----------void chang(int l,int r,int k){ int m=(l+r)/2; struct nn ltre=tree[k*2],rtre=tree[k*2+1]; //父节点的长度一定是从左右子节点的最长长度和跨越子节点的长度产生 tree[k].LL=ltre.LL; tree[k].RR=rtre.RR; tree[k].blen=max(ltre.blen,rtre.blen); tree[k].wlen=max(ltre.wlen,rtre.wlen); if(ltre.RR.c=='w'&&rtre.LL.c=='w')//当中间连续为白色时 { if(ltre.LL.c=='w'&<re.LL.len==m-l+1)//最左边长度 tree[k].LL.len=ltre.LL.len+rtre.LL.len; if(rtre.RR.c=='w'&&rtre.RR.len==r-m)//最右边长度 tree[k].RR.len=ltre.RR.len+rtre.RR.len; tree[k].wlen=max(tree[k].wlen,ltre.RR.len+rtre.LL.len); } else if(ltre.RR.c=='b'&&rtre.LL.c=='b')//当中间连续为黑色时 { if(ltre.LL.c=='b'&<re.LL.len==m-l+1) tree[k].LL.len=ltre.LL.len+rtre.LL.len; if(rtre.RR.c=='b'&&rtre.RR.len==r-m) tree[k].RR.len=ltre.RR.len+rtre.RR.len; tree[k].blen=max(tree[k].blen,ltre.RR.len+rtre.LL.len); }}//--------初始时建树，全定白色-----------void set_tree(int l,int r,int k){ tree[k].wlen=r-l+1; tree[k].blen=0; tree[k].LL.c='w'; tree[k].LL.len=r-l+1; tree[k].RR.c='w'; tree[k].RR.len=r-l+1; tree[k].need=0; if(l==r) return ; int m=(l+r)/2; set_tree(l,m,k*2); set_tree(m+1,r,k*2+1);}//-------当父节点的need=1时，表明左右子节点要更新异或-------void child_sepw(int l,int r,int k){ int m=(l+r)/2; if(tree[2*k].need)//当左节点的need也为1时，左节点的左右子节点也须要异或 tree[2*k].need=0;//但须要异或两次则变回原来，那么就不须要异或，就把need变成0 else tree[k*2].need=1;//否则左节点的左右子节点须要异或 if(l==m)tree[k*2].need=0; sepw(k*2); //异或左节点 if(tree[2*k+1].need) tree[2*k+1].need=0; else tree[k*2+1].need=1; if(m+1==r)tree[k*2+1].need=0; sepw(k*2+1);}//------查找L~R段的最长连续黑色是否跨越了节点K的左右子节点------int searchL_to_R(int len,int m,int k,int L,int R){ if(tree[2*k].RR.c=='b'&&tree[2*k+1].LL.c=='b') if(L<=m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len<=R) len=max(tree[2*k].RR.len+tree[k*2+1].LL.len,len); else if(L<=m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len>R) len=max(tree[2*k].RR.len+R-m,len); else if(L>m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len<=R) len=max(m-L+1+tree[k*2+1].LL.len,len); else len=R-L+1; return len;}//------x=1时是异或段L~R，x=0时是查找段L~R内的最长黑色长度-----int len,x;void chang_color(int l,int r,int k,int L,int R){ int m=(l+r)/2; if(L<=l&&r<=R){ if(x==1){ if(tree[k].need) child_sepw(l,r,k); tree[k].need=1; sepw(k); if(l==r)tree[k].need=0; } else len=max(tree[k].blen,len); return ; } if(tree[k].need) child_sepw(l,r,k); if(R<=m) chang_color(l,m,2*k,L,R); else if(L>m) chang_color(m+1,r,2*k+1,L,R); else{ chang_color(l,m,2*k,L,R); chang_color(m+1,r,2*k+1,L,R); if(x==0) len=searchL_to_R(len,m,k,L,R); } chang(l,r,k); tree[k].need=0;}int main(){ int n,m,i,nc[N],L,R;//vector<int>nc; while(scanf("%d",&n)>0) { set_tree(1,n,1); //nc.clear(); for(i=1;i<=n;i++) scanf("%d",&nc[i]); //{nc.push_back(c);} for(i=1;i<=n;i++) if(nc[i]) { L=i; while(nc[i+1]&&i+1<=n) i++; R=i; x=1; chang_color(1,n,1,L,R); } scanf("%d",&m); while(m--) { scanf("%d%d%d",&x,&L,&R); if(x==0) { len=0; chang_color(1,n,1,L,R); printf("%d\n",len); } else chang_color(1,n,1,L,R); } }}