本文共 2137 字，大约阅读时间需要 7 分钟。
首先，显然每个区间的最长连续子区间要么在左孩子里，要么在右孩子里，要么跨越两个孩子。于是我们可以对每个区间维护如下信息ll(left long),rl(rigth long),ml(mid long)分别表示前缀最长长度，后缀最长长度，中间的最长区间长度，并维护即可。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 13 using namespace std;14 15 struct Tree{16 int l,r;17 int ll,rl,ml;18 };19 20 int n,m;21 Tree T[400007];22 23 void buildtree(int now,int l,int r){24 T[now].ll=T[now].rl=T[now].ml=r-l+1;25 T[now].l=l;26 T[now].r=r;27 if (l==r) return;28 buildtree(now<<1,l,(l+r)>>1);29 buildtree((now<<1)|1,((l+r)>>1)+1,r);30 }31 32 void update(int now,int aim,int val){33 if (T[now].l==T[now].r){34 T[now].ll=T[now].rl=T[now].ml=val;35 return;36 }37 int mid=(T[now].l+T[now].r)>>1;38 if (aim<=mid) update(now<<1,aim,val);39 else update((now<<1)|1,aim,val);40 T[now].ll=T[now<<1].ll;41 T[now].rl=T[(now<<1)|1].rl;42 if (T[now<<1].ll==(T[now<<1].r-T[now<<1].l+1)) T[now].ll=T[now].ll+T[(now<<1)|1].ll;43 if (T[(now<<1)|1].rl==T[(now<<1)|1].r-T[(now<<1)|1].l+1) T[now].rl+=T[now<<1].rl;44 T[now].ml=max(T[now<<1].ml,T[(now<<1)|1].ml);45 T[now].ml=max(T[now].ml,T[now<<1].rl+T[(now<<1)|1].ll);46 }47 48 int query(int now,int aim){49 if (T[now].l==T[now].r || T[now].ml==0 || T[now].ml==T[now].r-T[now].l+1){50 return T[now].ml;51 }52 int mid=(T[now].l+T[now].r)>>1;53 if (aim<=mid){54 if (aim>=T[now<<1].r-T[now<<1].rl+1)55 return query(now<<1,aim)+query((now<<1)|1,mid+1);56 else57 return query(now<<1,aim);58 }59 else{60 if (aim<=T[(now<<1)|1].l+T[(now<<1)|1].ll-1)61 return query((now<<1)|1,aim)+query(now<<1,mid);62 else63 return query((now<<1)|1,aim);64 }65 }66 67 int main(){68 scanf("%d%d",&n,&m);69 buildtree(1,1,n);70 for (int cas=1;cas<=m;cas++){71 int f,x;72 scanf("%d%d",&f,&x);73 if (f==0){74 update(1,x,0);75 }76 if (f==1){77 update(1,x,1);78 }79 if (f==2){80 printf("%d\n",query(1,x));81 }82 checktree(1,1,n);83 }84 return 0;85 }86 /*87 5 388 2 289 0 390 2 291 92 5 593 2 294 0 395 2 296 1 397 2 298 */
转载于:https://www.cnblogs.com/baby-mouse/p/4555910.html