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

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

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

Tunnel Warfare

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 8361		Accepted: 3453

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

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;
}