HDU 1540 Tunnel Warfare(线段树,单点更新,区间查询)

Problem 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

题意:D k表示破坏村庄k,R表示恢复上次破坏的村庄,Q k表示查询包括k在内连续村庄的长度。

题解:分别维护左端点序列maxo[]和右端点序列mino[].

破坏/修复一个村子k的时候更新对应段的最大/最小值。破坏的时候把对应点的mino[]和maxo[]变成k。修复的时候把mino[]变成n+1,maxo[]变成0.

这样查询k时[1,k]中maxo[]的最大值代表k的左端点。[k,n]中的mino[]最小值代表k的右端点。

就相当于对坏掉的村庄做处理。查询村庄的时候分别找到左边和右边离它最近的。

比如查询k就找[1,k]中被破坏掉的最右边的点和[k,n]中被破坏掉的最左边的点。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50010;
#define lson l , m , num << 1
#define rson m + 1 , r , num << 1|1
int n , m , k , maxo[maxn << 2] , mino[maxn << 2];char s[2];
void up(int num){maxo[num] = max(maxo[num << 1] , maxo[num << 1|1]); mino[num] = min(mino[num << 1] ,mino[num << 1|1]);}
void built(int l , int r , int num){
    if(l == r) {maxo[num] = 0 ; mino[num] = n + 1;return;}
    int m = (l + r)>>1;
    built(lson);built(rson);
    up(num);
    return;
}
void des(int k , int l , int r , int num){
    if(l == r){maxo[num] = k; mino[num] = k;return;}
    int m = (l + r)>>1; if(k <= m) des(k,lson); if(k > m)des(k,rson);up(num);
}
void red(int k , int l , int r , int num){
    if(l == r){maxo[num] = 0; mino[num] = n + 1;return;}
    int m = (l + r)>>1; if(k <= m) red(k,lson); if(k > m)red(k,rson);up(num);
}
int getl(int L , int R , int l , int r , int num){
    if(L <= l && r <= R){return maxo[num];}
    int ans = 0;int m = (l + r) >> 1; if(L <= m) ans = max(ans , getl(L , R , lson));
    if(R > m) ans = max(ans , getl(L , R , rson));
    return ans;
}
int getr(int L , int R , int l , int r , int num){
    if(L <= l && r <= R){return mino[num];}
    int ans = n + 1;int m = (l + r) >> 1; if(L <= m) ans = min(ans , getr(L , R , lson));
    if(R > m) ans = min(ans , getr(L , R , rson));
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        built(1 , n , 1);
        stack<int>q;
        while(m--){
            scanf("%s",s);
            if(s[0] == ‘D‘){
                 scanf("%d",&k); des(k , 1 , n , 1);
                 q.push(k);
            }
            if(s[0] == ‘R‘){
                if(q.empty()){
                    continue;
                }
                k = q.top(); q.pop();
                red(k , 1 , n , 1);
            }
            if(s[0] == ‘Q‘){
                scanf("%d",&k);
                int ll = getl(1 , k , 1 , n , 1);
                int rr = getr(k , n , 1 , n , 1);
                int ans = rr - ll - 1;
                if(ans < 0) ans = 0;
                printf("%d\n",ans);
            }
        }
    }
}

时间: 03-11

HDU 1540 Tunnel Warfare(线段树,单点更新,区间查询)的相关文章

hdu 1540 Tunnel Warfare 线段树 单点更新,查询区间长度,区间合并

Tunnel Warfare Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1540 Description During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast areas of north China Plain. Gene

hdu 1540 Tunnel Warfare(线段树)

题目链接:hdu 1540 Tunnel Warfare 题目大意:有连续的N个城镇,三种操作: D x:第x城镇被破坏 Q x:插叙第x城镇所在联通块有多少个城镇没有被破坏 R:修复最后一个被破坏的城镇 解题思路:线段树区间合并,每个城镇看成一个叶子节点,用一个vector记录破坏顺序.对于查询来说,每次只要判断是否在mid?R[lson(u)],mid+L[rson(u)]之间即可,否则即递归查询左右子树. #include <cstdio> #include <cstring>

HDU 1540 Tunnel Warfare 线段树区间合并

Tunnel Warfare 题意:D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少 思路:一个节点的最大连续区间由(左儿子的最大的连续区间,右儿子的最大连续区间,左儿子的最大连续右区间+右儿子的最大连续左区间)决定 所以线段树的节点应该维护当前节点的最大连续左区间,最大连续右区间,和最大连续区间. 注意更新的时候,如果左儿子全满,父亲节点的左连续区间还要加上右儿子的左区间.反之同理. 查询的时候,可以剪枝,如果是叶子,或为空,或满,则不用往下查询. 查询

HDU 1540 Tunnel Warfare (线段树或set水过)

题意:D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少. 析:首先可以用set水过,set用来记录每个被破坏的村庄,然后查找时,只要查找左右两个端点好. 用线段树的话,就维护三个值分别是左端点连续右端点连续,全连续的最长的区别,然后用线段树维护就好. 代码如下: set过: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #includ

hdu 1540 Tunnel Warfare 线段树 区间合并

题意: 三个操作符 D x:摧毁第x个隧道 R x:修复上一个被摧毁的隧道,将摧毁的隧道入栈,修复就出栈 Q x:查询x所在的最长未摧毁隧道的区间长度. 1.如果当前区间全是未摧毁隧道,返回长度 2.如果在坐儿子的右区间或右儿子的左区间,返回这两个区间长度和 3.继续递归 #include <bits/stdc++.h> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std;

POJ 3264 Balanced Lineup (线段树单点更新 区间查询)

Balanced Lineup Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 36820   Accepted: 17244 Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer Joh

hdu 2795 Billboard(线段树单点更新)

Billboard Time Limit: 20000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14337    Accepted Submission(s): 6148 Problem Description At the entrance to the university, there is a huge rectangular billboard of

HDU1166(线段树单点更新区间查询)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 62483    Accepted Submission(s): 26386 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就

hdu 2795 Billboard(线段树+单点更新)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795 Billboard Time Limit: 20000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13050    Accepted Submission(s): 5651 Problem Description At the entrance to the un

HDU2852_KiKi&#39;s K-Number(线段树/单点更新)

解题报告 题目传送门 题意: 意思很好理解. 思路: 每次操作是100000次,数据大小100000,又是多组输入.普通模拟肯定不行. 线段树结点记录区间里存在数字的个数,加点删点操作就让该点个数+1,判断x存在就查询[1,x]区间的个数和[1,x-1]的个数. 求x之后第k大的数就先确定小于x的个数t,第t+k小的数就是要求的. #include <iostream> #include <cstdio> #include <cstring> using namespa