HDU 1540 Tunnel Warfare (线段树 / 求最大连续区间长度)

本文主要是介绍HDU 1540 Tunnel Warfare (线段树 / 求最大连续区间长度)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意： 抗日战争时期，华北平原广大地区进行了广泛的隧道战争。一般来说，通过隧道连接的村庄成一直线。除了两端的两个村外，每个村庄都与两个相邻的村直接相连。
入侵者经常对一些村庄发动袭击，并摧毁其中的部分隧道。八路军指挥官要求提供隧道和村庄的最新连接状态。如果某些村庄被严重隔离，则必须立即恢复连接！

输入：
输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。接下来的m行中的每行都描述一个事件。
下面以不同的格式描述了三个不同的事件：

D x：第x个村庄被摧毁。
问：陆军司令部要求第x个村庄包括其自身直接或间接联系的村庄数。
R：最后被摧毁的村庄被重建。

思路： 就是个常规线段树题目，和acwing上的你能回答这些问题吗做法原理相似。

代码实现：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define null NULL
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int   mod = 1e9 + 7;
const int  N = 50005;int n, m, x, tt;
char op[3];
stack<int> st;struct node{int l, r;int lmax, rmax, tmax;
}tr[N << 2];//区间合并
void pushdown(int u){tr[u].lmax = tr[u << 1].lmax;tr[u].rmax = tr[u << 1 | 1].rmax;if(tr[u << 1].lmax == tr[u << 1].r - tr[u << 1].l + 1) tr[u].lmax = tr[u << 1].lmax + tr[u << 1 | 1].lmax;if(tr[u << 1 | 1].rmax == tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) tr[u].rmax = tr[u << 1].rmax + tr[u << 1 | 1].lmax;tr[u].tmax = max(tr[u].rmax, tr[u].lmax);tr[u].tmax = max(tr[u].tmax, tr[u << 1].rmax + tr[u << 1 | 1].lmax);
}void build(int u, int l, int r)
{int t = r - l + 1;tr[u] = {l, r, t, t, t};if(l == r) return;int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}void modify(int u, int x, int v)
{if(tr[u].l == x && tr[u].r == x){tr[u].lmax = tr[u].rmax = tr[u].tmax = v;return;}int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u << 1, x, v);else modify(u << 1 | 1, x, v);//主义在修改后将两个区间合并pushdown(u);
}int query(int u, int x)
{if(!tr[u].tmax) return 0;//在左端区间if(x < tr[u].l + tr[u].lmax)return tr[u].lmax;//在右端区间if(x > tr[u].r - tr[u].rmax)return tr[u].rmax;//在两个区间的中间if(x > tr[u << 1].r - tr[u << 1].rmax && x < tr[u << 1 | 1].l + tr[u << 1 | 1].lmax)return tr[u << 1].rmax + tr[u << 1 | 1].lmax;int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) return query(u << 1, x);else return query(u << 1 | 1, x);
}int main()
{while(~scanf("%d%d", &n, &m)){while(!st.empty()) st.pop();build(1, 1, n);while(m --){scanf("%s", op);if(*op == 'D'){scanf("%d", &x);st.push(x);modify(1, x, 0);}else if(*op == 'Q'){scanf("%d", &x);printf("%d\n", query(1, x));}else if(!st.empty()){x = st.top(); st.pop();modify(1, x, 1);}}}return 0;
}