HDU 1540 Tunnel Warfare 线段树区间合并

Tunnel Warfare

题意:D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少

思路:一个节点的最大连续区间由(左儿子的最大的连续区间,右儿子的最大连续区间,左儿子的最大连续右区间+右儿子的最大连续左区间)决定

所以线段树的节点应该维护当前节点的最大连续左区间,最大连续右区间,和最大连续区间。

注意更新的时候,如果左儿子全满,父亲节点的左连续区间还要加上右儿子的左区间。反之同理。

查询的时候,可以剪枝,如果是叶子,或为空,或满,则不用往下查询。

查询的时候还要注意,当前查询点在左儿子的最大右连续区间内时,最大连续区间还要加上右儿子的最大连续区间。反之同理;

  1 // #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <sstream>
  6 #include <string>
  7 #include <algorithm>
  8 #include <list>
  9 #include <map>
 10 #include <vector>
 11 #include <queue>
 12 #include <stack>
 13 #include <cmath>
 14 #include <cstdlib>
 15 // #include <conio.h>
 16 using namespace std;
 17 #define clc(a,b) memset(a,b,sizeof(a))
 18 #define inf 0x3f3f3f3f
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N = 50010;
 22 const int MOD = 1e9+7;
 23 #define LL long long
 24 #define mi() (l+r)>>1
 25 double const pi = acos(-1);
 26 void fre() {
 27     freopen("in.txt","r",stdin);
 28 }
 29 // inline int r() {
 30 //     int x=0,f=1;char ch=getchar();
 31 //     while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1;ch=getchar();}
 32 //     while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘;ch=getchar();}return x*f;
 33 // }
 34 int s[N];
 35 struct node {
 36     int l,r;
 37     int ls,rs,ms;
 38 } e[N<<2];
 39
 40 void pushup(int rt) {
 41
 42 }
 43 void build(int l,int r,int rt) {
 44     e[rt].l=l;
 45     e[rt].r=r;
 46     e[rt].ls=e[rt].rs=e[rt].ms=r-l+1;
 47     if(l!=r) {
 48         int mid=mi();
 49         build(lson);
 50         build(rson);
 51     }
 52 }
 53
 54 void update(int rt,int c,int x) {
 55     if(e[rt].l==e[rt].r) {
 56         if(x>0) {
 57             e[rt].ls=e[rt].rs=e[rt].ms=1;
 58         } else
 59             e[rt].ls=e[rt].rs=e[rt].ms=0;
 60         return;
 61     }
 62     int mid=(e[rt].l+e[rt].r)>>1;
 63     if(c<=mid) {
 64         update(rt<<1,c,x);
 65     } else
 66         update(rt<<1|1,c,x);
 67     e[rt].ls=e[rt<<1].ls;
 68     e[rt].rs=e[rt<<1|1].rs;
 69     e[rt].ms=max(max(e[rt<<1].ms,e[rt<<1|1].ms),e[rt<<1].rs+e[rt<<1|1].ls);
 70     if(e[rt<<1].ls==e[rt<<1].r-e[rt<<1].l+1) {
 71         e[rt].ls+=e[rt<<1|1].ls;
 72     }
 73     if(e[rt<<1|1].rs==e[rt<<1|1].r-e[rt<<1|1].l+1) {
 74         e[rt].rs+=e[rt<<1].rs;
 75     }
 76 }
 77
 78 int query(int rt,int c) {
 79     if(e[rt].l==e[rt].r||e[rt].ms==0||e[rt].ms==e[rt].r-e[rt].l+1) {
 80         return e[rt].ms;
 81     }
 82     int mid=(e[rt].l+e[rt].r)>>1;
 83     if(c<=mid) {
 84         if(c>=e[rt<<1].r-e[rt<<1].rs+1) {
 85             return query(rt<<1,c)+query(rt<<1|1,mid+1);
 86         } else
 87             return query(rt<<1,c);
 88     } else {
 89         if(c<=e[rt<<1|1].l+e[rt<<1|1].ls-1) {
 90             return query(rt<<1|1,c)+query(rt<<1,mid);
 91         } else
 92             return query(rt<<1|1,c);
 93     }
 94 }
 95 int main() {
 96 //    fre();
 97     int n,q,top;
 98     while(~scanf("%d%d",&n,&q)) {
 99         build(1,n,1);
100         top=0;
101         while(q--) {
102             char c;
103             int x;
104             cin>>c;
105             if(c==‘D‘) {
106                 cin>>x;
107                 s[top++]=x;
108                 update(1,x,0);
109             } else if(c==‘Q‘) {
110                 cin>>x;
111                 printf("%d\n",query(1,x));
112             } else {
113                 x=s[--top];
114                 update(1,x,1);
115             }
116         }
117     }
118     return 0;
119 }
时间: 06-30

HDU 1540 Tunnel Warfare 线段树区间合并的相关文章

HDU 1540 Tunnel Warfare(线段树 区间合并 最大连续区间)

题意  有n个连在一起的地道  接下来有m个操作  D x 炸掉x号地道  炸掉后x所在的区间就不连续了  Q x 查询输出包括x的最大连续区间长度   R修复最后一个被炸的地道  注意输入R时可能并没有需要修复的地道 线段树的区间合并问题  线段树要维护3个信息 len  对应区间的最大连续长度 ll  对应区间最左端的一段连续长度 lr  对应区间最右端的一段连续长度 那么双亲节点的这些信息和孩子节点有什么关系呢  容易发现 双亲的len 是 左孩子的len 右孩子的len  左孩子的右端长

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;

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 vill

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 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 线段树:单点更新,区间合并

Tunnel Warfare                                  Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Problem Description During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast

HDU 1540 POJ 2892 线段树区间合并

给出N个点,M次操作,N个点开始在一条线上链式相连 D操作  把某点删除掉 Q操作  询问某点一共可以连接多少个点 R操作  把上一次删除的点还原 线段树处理区间合并 分别记录每个区间的左端连续最长和右端连续最长 #include "stdio.h" #include "string.h" struct node { int l,r,lx,rx,x; }data[200010]; int mark[50100]; int Max(int a,int b) { if

Tunnel Warfare 线段树 区间合并|最大最小值

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 con

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

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