给出N个点，M次操作，，N个点开始在一条线上链式相连
D操作 把某点删除掉
Q操作 询问某点一共可以连接多少个点
R操作 把上一次删除的点还原
线段树处理区间合并
分别记录每个区间的左端连续最长和右端连续最长
#include "stdio.h"#include "string.h"struct node{int l,r,lx,rx,x;}data[200010];int mark[50100];int Max(int a,int b){if (a<b) return b;else return a;}void build(int l,int r,int k){int mid;data[k].l=l;data[k].r=r;data[k].lx=data[k].rx=data[k].x=data[k].r-data[k].l+1;if (l==r) return ;mid=(l+r)/2;build(l,mid,k*2);build(mid+1,r,k*2+1);}void updata(int x,int k,int op){int mid,ll,rr;if (data[k].l==data[k].r){data[k].lx=data[k].rx=data[k].x=op;return ;}mid=(data[k].l+data[k].r)/2;if (x<=mid) updata(x,k*2,op);elseif (x>mid) updata(x,k*2+1,op);ll=data[k*2].r-data[k*2].l+1;rr=data[k*2+1].r-data[k*2+1].l+1;data[k].lx=data[k*2].lx;if (data[k*2].lx==ll) data[k].lx+=data[k*2+1].lx;data[k].rx=data[k*2+1].rx;if (data[k*2+1].rx==rr) data[k].rx+=data[k*2].rx;data[k].x=Max(Max(data[k*2].x,data[k*2+1].x),data[k*2].rx+data[k*2+1].lx);}int query(int x,int k){int mid;if (data[k].l==data[k].r || data[k].x==0 || data[k].x==data[k].r-data[k].l+1)return data[k].x;mid=(data[k].l+data[k].r)/2;if (x<=mid){if (data[k*2].r-x+1<=data[k*2].rx)return query(x,k*2)+query(mid+1,k*2+1);elsereturn query(x,k*2);}else{if (x-data[k*2+1].l+1<=data[k*2+1].lx)return query(x,k*2+1)+query(mid,k*2);elsereturn query(x,k*2+1);}}int main(){int cnt,n,m,x;char ch[10];while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);cnt=0;while (m–){scanf("%s",ch);if (ch[0]=='D'){scanf("%d",&x);mark[cnt++]=x;updata(x,1,0);}if (ch[0]=='Q'){scanf("%d",&x);printf("%d\n",query(x,1));}if (ch[0]=='R'){cnt–;if (cnt<0) cnt=0;else updata(mark[cnt],1,1);}}}return 0;}
旅行，有一种苍凉，“浮云游子意，落日故人情”，
