I - Tunnel Warfare

HDU - 1540

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50010

using namespace std;

int n,m,top;

int stack[MAXN],vis[MAXN];

struct nond{

    int l,r,len,ren,mid;

}tree[MAXN*];

void build(int now,int l,int r){

    tree[now].l=l;tree[now].r=r;

    tree[now].len=tree[now].r-tree[now].l+;

    tree[now].ren=tree[now].mid=tree[now].len;

    if(tree[now].l==tree[now].r)    return ;

    int mid=(tree[now].l+tree[now].r)/;

    build(now*,l,mid);

    build(now*+,mid+,r);

}

void change(int now,int x,int pos){

    if(tree[now].l==tree[now].r){

        tree[now].len=tree[now].ren=tree[now].mid=pos;

        return ;

    }

    int mid=(tree[now].l+tree[now].r)/;

    if(x<=mid)    change(now*,x,pos);

    else if(x>mid)    change(now*+,x,pos);

    tree[now].len=tree[now*].len;

    tree[now].ren=tree[now*+].ren;

    tree[now].mid=max(tree[now*].mid,tree[now*+].mid);

    tree[now].mid=max(tree[now].mid,tree[now*].ren+tree[now*+].len);

    if(tree[now*].len==tree[now*].r-tree[now*].l+)

        tree[now].len=tree[now*].len+tree[now*+].len;

    if(tree[now*+].ren==tree[now*+].r-tree[now*+].l+)

        tree[now].ren=tree[now*+].ren+tree[now*].ren;

}

int query(int now,int k){

    if(tree[now].l==tree[now].r||tree[now].mid==||tree[now].mid==tree[now].r-tree[now].l+)

        return tree[now].mid;

    int mid=(tree[now].l+tree[now].r)/;

    if(k<=mid){

        if(k>=tree[now*].r-tree[now*].ren+)

            return query(now*,k)+query(now*+,mid+);

        else return query(now*,k);

    }

    else{

        if(k<=tree[now*+].l+tree[now*+].len-)

            return query(now*+,k)+query(now*,mid);

        else return query(now*+,k);

    }

}

int main(){

    while(scanf("%d%d",&n,&m)!=EOF){

        build(,,n);top=;

        for(int i=;i<=m;i++){

            char c;int x;

            scanf("\n%c",&c);

            if(c=='D'){

                scanf("%d",&x);

                stack[++top]=x;change(,x,);

            }

            else if(c=='Q'){

                scanf("%d",&x);

                printf("%d\n",query(,x));

            }

            else change(,stack[top--],);

        }

    }

}

/*

7 9

D 3

D 6

D 5

Q 4

Q 5

R

Q 4

R

Q 4

*/