Problem Description

During the War of Resistance Against Japan, tunnel warfare wascarried out extensively in the vast areas of north China Plain.Generally speaking, villages connected by tunnels lay in a line.Except the two at the ends, every village was directly connectedwith
two neighboring ones.

Frequently the invaders launched attack on some of the villages anddestroyed the parts of tunnels in them. The Eighth Route Armycommanders requested the latest connection state of the tunnels andvillages. If some villages are severely isolated, restoration
ofconnection must be done immediately!

 

Input

The first line of the input contains two positive integers nand m (n, m ≤ 50,000) indicating the number of villages and events.Each of the next m lines describes an event.

There are three different events described in different formatshown below:

D x: The x-th village was destroyed.

Q x: The Army commands requested the number of villages that x-thvillage was directly or indirectly connected with includingitself.

R: The village destroyed last was rebuilt.

 

Output

Output the answer to each of the Army commanders’ request inorder on a separate line.

 

Sample Input

 

Sample Output

 

Source

    //这个信息应该可以不保存

然后就是结点的更新与查找了，具体看代码的操作。

#include<stdio.h>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define MAXN 50001

struct{
    int s;
    int s_left;
    int s_right;
}Node[MAXN<<2];

int c[MAXN];

void PushUp(int l,int r,int rt)
{
    int m=(l+r)>>1;
    Node[rt].s=Node[rt<<1].s_right+Node[rt<<1|1].s_left;
    Node[rt].s_left=Node[rt<<1].s_left;
    if(Node[rt<<1].s_left==m-l+1)
        Node[rt].s_left+=Node[rt<<1|1].s_left;
    Node[rt].s_right=Node[rt<<1|1].s_right;
    if(Node[rt<<1|1].s_right==r-m)
        Node[rt].s_right+=Node[rt<<1].s_right;
}

void build(int l,int r,int rt)
{
    Node[rt].s=r-1+1;
    Node[rt].s_left=r-l+1;
    Node[rt].s_right=r-l+1;
    if(l==r)
    {
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}

void update(int a,int tmp,int l,int r,int rt)
{
    if(l==r)
    {
        Node[rt].s=a;
        Node[rt].s_left=a;
        Node[rt].s_right=a;
        return;
    }
    int m=(l+r)>>1;
    if(tmp<=m)
        update(a,tmp,lson);
    else
        update(a,tmp,rson);
    PushUp(l,r,rt);
}

int query(int tmp,int l,int r,int rt)
{
    if(tmp-l+1<=Node[rt].s_left)
        return Node[rt].s_left;
    if(r-tmp+1<=Node[rt].s_right)
        return Node[rt].s_right;
    if(l==r)
        return Node[rt].s;
    int m=(l+r)>>1;
    if(tmp<=m)
        if(m-tmp+1<=Node[rt<<1].s_right)
            return Node[rt].s;
        else
            return query(tmp,lson);
    else
        if(tmp-m<=Node[rt<<1|1].s_left)
            return Node[rt].s;
        else
            return query(tmp,rson);
}

int main(void)
{
    int n,m,count,i,a;
    char ch[10];
//    freopen("d:\\in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)==2)
    {
        build(1,n,1);
        count=0;
        for(i=1;i<=m;i++)
        {
            scanf("%s",ch);
            if(ch[0]=='D')
            {
                scanf("%d",&a);
                c[++count]=a;
                update(0,a,1,n,1);
            }
            else if(ch[0]=='R')
            {
                if(count>0)
                    update(1,c[count--],1,n,1);
            }
            else
            {
                scanf("%d",&a);
                printf("%d\n",query(a,1,n,1));
            }
        }
    }
    return 0;
}