POJ 2892-Tunnel Warfare（线段树单点更新-炸毁修复城市隧道）

向右看齐 2022-06-17 04:18 166阅读 0赞

Tunnel Warfare

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;8361</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3453</td> 
  </tr> 
 </tbody> 
</table>

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:

1.  D x: The *x*\-th village was destroyed.
2.  Q x: The Army commands requested the number of villages that *x*\-th village was directly or indirectly connected with including itself.
3.  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

## 题目意思： ##

N个城市相互连通，D X表示炸毁城市X与其他城市的连接，R X表示恢复上一个最后炸毁的城市的连接，Q X表示查询城市X与邻近 有多少个连续的其他城市。

## 解题思路： ##

线段树，单点更新。

节点保存llen和rlen表示该节点左右两侧连续节点的个数。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 500005
    int sta[MAXN];//修复栈
    struct Node //树
    {
        int l,r;//左右节点
        int llen,rlen;//区间内的城市情况,连续个1的个数
    };
    Node tree[MAXN<<2];
    void PushUP(int i)//向上更新父节点的值
    {
        tree[i].llen=tree[2*i].llen ;
        tree[i].rlen=tree[2*i+1].rlen ;
        if(tree[2*i].llen==tree[2*i].r-tree[2*i].l+1)//区间连续
            tree[i].llen+=tree[2*i+1].llen;
        if(tree[2*i+1].rlen==tree[2*i+1].r-tree[2*i+1].l+1)
            tree[i].rlen+=tree[2*i].rlen;
    }
    void BuildTree(int i, int l, int r)//建树
    {
        tree[i].l=l;
        tree[i].r=r;
        if(l==r)
        {
            tree[i].llen=tree[i].rlen=1;//初始状态都是连通的
            return ;
        }
        BuildTree(2*i,l,(l+r)/2);
        BuildTree(2*i+1,(l+r)/2+1,r);
        PushUP(i);//继续更新
    }
    void Update(int i,int l,int r,int t,int op)
    {
        if(tree[i].l==tree[i].r)
        {
            tree[i].llen=tree[i].rlen=op;
            return ;
        }
        int mid=(tree[i].l+tree[i].r)/2;
        if(t<=mid)
            Update(2*i,l,r,t,op);
        else
            Update(2*i+1,l,r,t,op);
        PushUP(i);//修改完后，仍然要向上修正父节点的值
    }
    int Query(int i,int l,int r,int t)
    {
        if(tree[i].l==tree[i].r)
            return tree[i].llen;
        int mid=(tree[i].l+tree[i].r)/2;
        if(t<=mid)
        {
            if(tree[2*i].r-tree[2*i].rlen+1<=t)//t被包含在左子树连续区间内
                return tree[2*i].rlen+tree[2*i+1].llen;
            Query(2*i,l,r,t);
        }
        else
        {
            if(tree[2*i+1].llen+tree[2*i+1].l-1>=t)//t被包含在右子树连续区间内
                return tree[2*i].rlen+tree[2*i+1].llen;
            Query(2*i+1,l,r,t);
        }
    }
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int n,m;
        while(~scanf("%d%d\n",&n,&m))
        {
            BuildTree(1,1,n);//建树
            int cnt=0;
            for(int j=0; j<m; ++j)
            {
                char ch;
                cin>>ch;
                if(ch=='D')//摧毁
                {
                    int t;
                    scanf("%d\n",&t);
                    sta[cnt++]=t;
                    Update(1,1,n,t,0);
                }
                else if(ch=='Q')//查询
                {
                    int t;
                    scanf("%d\n",&t);
                    printf("%d\n",Query(1,1,n,t));
                }
                else if(ch=='R')//修复
                {
                    int t=sta[--cnt];//从栈中取出最后炸毁的序列号
                    Update(1,1,n,t,1);
                }
            }
        }
        return 0;
    }

[POJ Monthly--2006.07.30]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2006.07.30