Tunnel Warfare HDU - 1540 （线段树不同子树的合并）

在抗日战争期间，华北平原广大地区进行了大规模的隧道战。 一般来说，通过隧道连接的村庄排成一列。 除了两端，每个村庄都与两个相邻的村庄直接相连。

入侵者经常对一些村庄发动袭击并摧毁其中的部分隧道。 八路军指挥官要求最新的隧道和村庄连接状态。 如果某些村庄严重隔离，必须立即恢复连接！

Input

输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。 接下来的m行中的每一行描述一个事件。

以下所示的不同格式描述了三种不同的事件：

D x：第x个村庄被毁。

Q x：指挥官询问第x个村庄与其直接或间接相关的村庄数量。

R：最后毁坏的村庄被重建了。

Output

按顺序输出每个指挥官询问的答案。

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

分析：
维护每个节点所对应区间的左最长1串，右最长一串和区间最长1串。查询的时候如果当前区间最长1串长度为0或者满，直接返回0\满；如果x位于当前区间的“中部”（左孩子的右和右孩子的左连接而成），直接返回中部长度；除此以外就继续查找。
代码：

 #include <bits/stdc++.h>//题目也没说多组输入啊，WA了好多次，想哭

 using namespace std;

 const int maxn =  * 1e4 + ;

 struct node

 {

     int l, r;

     int ln, rn, mn;

 }t[maxn << ];

 int n, m;

 void pushup(int tar)

 {

     t[tar].ln = t[tar << ].ln, t[tar].rn = t[tar <<  | ].rn;

     t[tar].mn = max(t[tar << ].mn, t[tar <<  | ].mn);

     t[tar].mn = max(t[tar].mn, t[tar << ].rn + t[tar <<  | ].ln);

     if (t[tar << ].ln == t[tar << ].r - t[tar << ].l + ) t[tar].ln = t[tar << ].ln + t[tar <<  | ].ln;

     if (t[tar <<  | ].rn == t[tar <<  | ].r - t[tar <<  | ].l + ) t[tar].rn = t[tar <<  | ].rn + t[tar << ].rn;

 }

 void build(int l, int r, int tar)

 {

     t[tar].l = l, t[tar].r = r;

     t[tar].ln = t[tar].rn = t[tar].mn = r - l + ;

     if (l == r) return;

     int mid = (l + r) >> ;

     build(l, mid, tar << );

     build(mid + , r, tar <<  | );

 }

 void update(int x, int state, int tar)

 {

     if (t[tar].l == t[tar].r)

     {

         t[tar].ln = t[tar].rn = t[tar].mn = state;

         return;

     }

     int mid = (t[tar].l + t[tar].r) >> ;

     if (x <= mid) update(x, state, tar << );

     else if (x > mid) update(x, state, tar <<  | );

     pushup(tar);

 }

 int query(int x, int tar)//查询依据为，x必然存在于某个区间的中心部分，叶子节点除外，所以对叶子节点特判。

 {

          if (t[tar].l == t[tar].r) return 0;//如果是叶子节点直接输出0，说明     int mid = (t[tar].l + t[tar].r) >> ;

     if (x >= t[tar << ].r - t[tar << ].rn +  && x <= t[tar <<  | ].l + t[tar <<  | ].ln - ) return t[tar << ].rn + t[tar <<  | ].ln;

     else if (x <= mid) return query(x, tar << );

     else return query(x, tar <<  | );

 }

 int main()

 {

     int n, m;

     while (cin >> n >> m)

     {

         stack<int> s;

         char ope[];

         int x;

         build(, n, );

         while (m--)

         {

             cin >> ope;

             if (ope[] == 'D')

             {

                 cin >> x;

                 s.push(x);

                 update(x, , );

             }

             else if (ope[] == 'R')

             {

                 x = s.top();

                 s.pop();

                 update(x, , );

             }

             else

             {

                 cin >> x;

                 cout << query(x, ) << endl;

             }

         }

     }

 }

巴特西

Tunnel Warfare HDU - 1540 （线段树不同子树的合并）

最新文章

热门文章