n 个点 q个操作
Q u 问u所在的位置 连续1的个数 ( 初始化n个点都为1)
D u 把u点染成 0 色
R 把最后一次染的点染成1色
#include#include #include using namespace std; #define N 51000 #define L(x) (x<<1) #define R(x) (x<<1|1) inline int Max(int a,int b){return a>b a:b;} inline int Min(int a,int b){return a>1;} int len(){ return r-l+1;} int Llen, Rlen;//连续1的个数 1表示没破坏 }tree[N*4]; void updata_up(int id){ tree[id].Llen = tree[L(id)].Llen ; tree[id].Rlen = tree[R(id)].Rlen ; if( tree[L(id)].Llen == tree[L(id)].len() ) tree[id].Llen += tree[R(id)].Llen; if( tree[R(id)].Rlen == tree[R(id)].len() ) tree[id].Rlen += tree[L(id)].Rlen; } void build(int l, int r, int id){ tree[id].l = l, tree[id].r = r; if(l == r) { tree[id].Llen = tree[id].Rlen = 1; return ; } int mid = tree[id].mid(); build(l, mid, L(id)); build(mid+1, r, R(id)); updata_up(id); } void updata(int pos, int id, int oper){ if(tree[id].l == tree[id].r){ tree[id].Llen = tree[id].Rlen = oper; return ; } int mid = tree[id].mid(); if(pos <= mid)updata(pos, L(id), oper); else updata(pos, R(id), oper); updata_up(id); } int query(int pos, int id){ if(tree[id].l == tree[id].r) return tree[id].Llen; if(pos<= tree[id].mid()){ if(tree[L(id)].r - tree[L(id)].Rlen + 1 <= pos) return tree[L(id)].Rlen + tree[R(id)].Llen; else return query(pos, L(id)); } else { if(tree[R(id)].Llen + tree[R(id)].l - 1 > =pos) return tree[L(id)].Rlen + tree[R(id)].Llen; return query(pos, R(id)); } } int last[N],top; int main(){ int n,q,u; while(~scanf("%d %d",&n,&q)){ build(1,n,1); top = 1; while(q--){ char c = getchar(); while(c!='D' && c!='Q' && c!='R')c=getchar(); if(c=='D'){ scanf("%d",&u); updata(u, 1, 0); last[top++] = u; } else if(c == 'Q'){ scanf("%d",&u); printf("%d\n", query(u, 1)); } else if(top>1) updata(last[--top], 1, 1); } } return 0; } /* 10 99 Q 1 Q 2 D 2 Q 1 D 2 D 2 D 1 Q 1 Q 2 Q 3 R Q 1 Q 2 Q 3 R Q 1 Q 2 Q 3 R Q 1 Q 2 Q 3 ANS: 10 10 1 0 0 8 1 0 8 10 10 10 10 10 10 ------------ 3 100 D 3 D 1 D 2 R Q 1 Q 2 Q 3 R Q 1 Q 2 Q 3 ans: 0 1 0 2 2 0 */