POJ-2892-Tunnel Warfare(線段樹)

POJ-2892-Tunnel Warfare(線段樹)

Description

During the War of Resistance Against Japan, tunnel warfare was carried 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 connected with two neighboring ones.

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

Input

The first line of the input contains two positive integers n and 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 format shown below:

D x: The x-th village was destroyed.Q x: The Army commands requested the number of villages that x-th village was directly or indirectly connected with including itself.R: The village destroyed last was rebuilt.

Output

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

Sample Input

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

Sample Output

1
0
2
4

Hint

An illustration of the sample input:

      OOOOOOO

D 3   OOXOOOO

D 6   OOXOOXO

D 5   OOXOXXO

R     OOXOOXO

R     OOXOOOO

Source

POJ Monthly--2006.07.30, updog

思路：線段樹維護每個區間的左右兩端分別到中間的最大連續區間的大小，注意左右子樹可能存在最大連續區間大小就等於該節點的區間大小的情況。

#include 

struct{
int l,r;//分別記錄左右兩邊開始的最大連續區間大小
}node[200000];

int stk[50000],top,n,m;

void build(int idx,int s,int e)
{
    node[idx].l=node[idx].r=e-s+1;

    if(s!=e)
    {
        int mid=(s+e)>>1;

        build(idx<<1,s,mid);
        build(idx<<1|1,mid+1,e);
    }
}

void update(int idx,int s,int e,int pos,int val)
{
    if(s==e) node[idx].l=node[idx].r=val;//val為0代表摧毀村莊，為1代表修復村莊
    else
    {
        int mid=(s+e)>>1;

        if(pos<=mid) update(idx<<1,s,mid,pos,val);
        else update(idx<<1|1,mid+1,e,pos,val);

        if(node[idx<<1].l==mid-s+1) node[idx].l=mid-s+1+node[idx<<1|1].l;//左子樹滿了
        else node[idx].l=node[idx<<1].l;

        if(node[idx<<1|1].r==e-mid) node[idx].r=e-mid+node[idx<<1].r;//右子樹滿了
        else node[idx].r=node[idx<<1|1].r;
    }
}

int query(int idx,int s,int e,int pos)
{
    if(s==e) return 0;//如果到了葉子節點就肯定為0

    int mid=(s+e)>>1;

    if(pos<=mid)
    {
        if(pos>=mid-node[idx<<1].r+1) return node[idx<<1].r+node[idx<<1|1].l;//如果被包含在左子樹的右區間還要加上右子樹的左區間
        else return query(idx<<1,s,mid,pos);
    }
    else
    {
        if(pos<=mid+node[idx<<1|1].l) return node[idx<<1|1].l+node[idx<<1].r;//如果被包含在右子樹的左區間還要加上左子樹的右區間
        else return query(idx<<1|1,mid+1,e,pos);
    }
}

int main()
{
    int t;
    char s[5];

    while(~scanf("%d%d",&n,&m))
    {
        build(1,1,n);

        top=0;

        while(m--)
        {
            scanf("%s",s);

            if(s[0]=='D')
            {
                scanf("%d",&t);

                stk[top++]=t;

                update(1,1,n,t,0);
            }
            else if(s[0]=='R')
            {
                update(1,1,n,stk[--top],1);
            }
            else
            {
                scanf("%d",&t);

                printf("%d\n",query(1,1,n,t));
            }
        }
    }
}