HDOJ1540 Tunnel Warfare 线段树区间合并

HDOJ 1540

题目大意：给定两个整数N，M, 其中N表示一共有N个村庄，M代表有M次操作，操作有以下：

1. D x 销毁村庄x

2. Q x 询问与村庄x相邻的村庄总数

3. R 最近一次销毁的村庄得到重建

问题分析：

对于N个村庄，可以建立一颗线段树，维护最大连续区间长度，操作分析：

在线段树上找到x节点，并将x节点“销毁”（村庄x被销毁），然后分别更新与x节点（村庄x）相关联的节点值（这里指左右连续区间的长度）
对于询问操作，显然这里要求返回的是存在x的最大左右连续区间长度和
将村庄x恢复（具体到重置线段的覆盖标志），并更新与村庄x相关联的最大连续区间和

具体实现：

对于有N个村庄，可以建立区间为[1, N]的线段树，维护最大连续区间长度，节点里有这些信息需要维护：最大左连续区间长度，最大右连续区间长度，总对大连续区间长度，覆盖标志，每次PushUp都要将左右子区间进行合并，加入lazy-tag优化时间复杂度（简单来说就是将更新延迟到下一次询问或者需要更新的时候），对于R操作，因为该操作的对象是最近一次销毁的村庄，因此在每一次 D x 操作以后就将 x 进栈，等到 R 操作时就将栈顶弹出，于是操作对象就转移到栈顶元素

代码：

  1 #include <stack>
  2 #include <cstdio>
  3 using namespace std;
  4 
  5 #define lson l, m, rt<<1
  6 #define rson m+1, r, rt<<1|1
  7 
  8 const int maxn = 50000;
  9 
 10 char cmd[5];
 11 stack <int> st;
 12 int n, mNum, a;
 13 int lsum[maxn*3], rsum[maxn*3], sum[maxn*3], cover[maxn*3];
 14 
 15 int Max(int x, int y)
 16 {
 17     return (x>y ? x:y);
 18 }/* Max */
 19 
 20 void BuildTree(int l, int r, int rt)
 21 {
 22     cover[rt] = -1;
 23     lsum[rt] = rsum[rt] = sum[rt] = r-l+1;
 24     
 25     if (l == r)
 26         return ;
 27     
 28     int m = (l+r)>>1;
 29     BuildTree(lson);
 30     BuildTree(rson);
 31 }/* BuildTree */
 32 
 33 void PushDown(int rt, int k)
 34 {
 35     if (cover[rt] != -1)
 36     {
 37         cover[rt<<1] = cover[rt<<1|1] = cover[rt];
 38         lsum[rt<<1] = rsum[rt<<1] = sum[rt<<1] = cover[rt] ? 0:k-(k>>1);
 39         lsum[rt<<1|1] = rsum[rt<<1|1] = sum[rt<<1|1] = cover[rt] ? 0:(k>>1);
 40         cover[rt] = -1;
 41     }
 42 }/* PushDown */
 43 
 44 int Query(int p, int l, int r, int rt)
 45 {
 46     if (sum[rt]==0 || sum[rt]==r-l+1 || l==r)
 47         return sum[rt];
 48     
 49     PushDown(rt, r-l+1);
 50     
 51     int m = (l+r)>>1;
 52     if (p <= m)
 53     {
 54         if (p > m-rsum[rt<<1])
 55             return rsum[rt<<1]+Query(m+1, rson);
 56         else
 57             return Query(p, lson);
 58     }
 59     else
 60     {
 61         if (p <= m+lsum[rt<<1|1])
 62             return lsum[rt<<1|1]+Query(m, lson);
 63         else
 64             return Query(p, rson);
 65     }
 66 }/* Query */
 67 
 68 void PushUp(int rt, int k)
 69 {   /* 左右子区间合并 */ 
 70     lsum[rt] = lsum[rt<<1];
 71     rsum[rt] = rsum[rt<<1|1];
 72     
 73     if (lsum[rt] == k-(k>>1))
 74         lsum[rt] += lsum[rt<<1|1];
 75     if (rsum[rt] == (k>>1))
 76         rsum[rt] += rsum[rt<<1];
 77     
 78     sum[rt] = Max(rsum[rt<<1]+lsum[rt<<1|1], Max(sum[rt<<1], sum[rt<<1|1]));
 79 }/* PushUp */
 80 
 81 void UpData(int p, int c, int l, int r, int rt)
 82 {
 83     if (l == r)
 84     {
 85         lsum[rt] = rsum[rt] = sum[rt] = c ? 0:r-l+1;
 86         cover[rt] = c;
 87         
 88         return ;
 89     }/* End of If */
 90     
 91     PushDown(rt, r-l+1);
 92     
 93     int m = (l+r)>>1;
 94     if (p <= m)
 95         UpData(p, c, lson);
 96     else
 97         UpData(p, c, rson);
 98     
 99     PushUp(rt, r-l+1);
100 }/* UpData */
101 
102 int main()
103 {
104     while (~scanf("%d %d", &n, &mNum))
105     {
106         BuildTree(1, n, 1);
107         
108         while (!st.empty())
109             st.pop();
110         
111         for (int i=1; i<=mNum; ++i)
112         {
113             scanf("%s", cmd);
114             if (cmd[0] == 'Q')
115             {
116                 scanf("%d", &a);
117                 printf("%d\n", Query(a, 1, n, 1));
118             }
119             else if (cmd[0] == 'D')
120             {
121                 scanf("%d", &a);
122                 UpData(a, 1, 1, n, 1);
123                 st.push(a);
124             }
125             else
126             {
127                 a = st.top();
128                 st.pop();
129                 UpData(a, 0, 1, n, 1);
130             }
131         }/* End of For */
132     }/* End of While */    
133     
134     return 0;
135 }