93 lines
3.6 KiB
C++
93 lines
3.6 KiB
C++
#include <iostream>
|
||
#include <cstdio>
|
||
#include <cmath>
|
||
#include <stack>
|
||
using namespace std;
|
||
const int N = 50010;
|
||
struct Node {
|
||
int l, r;
|
||
int lmax, rmax; //定义：左（右）最大联通长度：从区间最左端（右）向右（左）前进，能联通的最大长度。
|
||
} tr[N << 2];
|
||
|
||
void pushup(int u) {
|
||
auto &root = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
|
||
// 下面这个定义和更新办法，真的是太妙了~
|
||
// root的左最大联通长度=左儿子ls的左最大联通长度+
|
||
// (1) 如果左儿子ls的左最大联通长度等于左侧总长度，那么还需要加上右儿子的左侧最大联通长度
|
||
// (2) 如果右儿子rs的右最大联通长度等于右侧总长度，那么还需要加上左儿子的右侧最大联通长度
|
||
root.lmax = ls.lmax + (ls.lmax == ls.r - ls.l + 1 ? rs.lmax : 0);
|
||
root.rmax = rs.rmax + (rs.rmax == rs.r - rs.l + 1 ? ls.rmax : 0);
|
||
}
|
||
|
||
void build(int u, int l, int r) {
|
||
tr[u] = {l, r}; //标准姿势记录范围
|
||
if (l == r) { //初始化构建时，每个叶子节点的左边最大，右边最大都是自己，长度是1
|
||
tr[u].lmax = tr[u].rmax = 1;
|
||
return;
|
||
}
|
||
int mid = (l + r) >> 1;
|
||
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
||
//因初始化左右最大不为0，需要向父节点更新统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//线段树单点更新
|
||
void modify(int u, int x, int v) {
|
||
if (tr[u].l == tr[u].r) {
|
||
tr[u].lmax = tr[u].rmax = 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);
|
||
pushup(u);
|
||
}
|
||
//线段树单点查询
|
||
int query(int u, int x) {
|
||
if (tr[u].l == tr[u].r) return tr[u].lmax; //查询到点,返回叶子节点上的记录最大值即可
|
||
int mid = (tr[u].l + tr[u].r) >> 1;
|
||
auto &ls = tr[u << 1], &rs = tr[u << 1 | 1];
|
||
/*
|
||
如果查询点落在左儿子区间中，则看它是否落在了右最长联通长度区间中。
|
||
若是，那么结果即为左儿子的右最长联通长度加上右儿子的左最长联通长度；若不是，那么继续向下查询。
|
||
同理得右。
|
||
*/
|
||
if (x <= mid) {
|
||
if ((ls.r - x) < ls.rmax)
|
||
return ls.rmax + rs.lmax;
|
||
else
|
||
return query(u << 1, x);
|
||
} else {
|
||
if ((x - ls.r) <= rs.lmax)
|
||
return rs.lmax + ls.rmax;
|
||
else
|
||
return query(u << 1 | 1, x);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
int n, m;
|
||
while (~scanf("%d%d", &n, &m)) {
|
||
stack<int> stk; //利用堆栈记录上一个是哪个
|
||
build(1, 1, n); //构建线段树
|
||
while (m--) {
|
||
char op[2]; //一般采用scanf进行读入char,都是开2个空间，读取op[0],防止有空格或换行导致错误
|
||
int x;
|
||
cin >> op;
|
||
if (op[0] == 'D') { //摧毁X位置的隧道
|
||
scanf("%d", &x);
|
||
modify(1, x, 0); //在以1为根的线段树中，单点修改X位置的隧道值为0
|
||
stk.push(x); //用堆栈记录操作，用于找出"前一个","再前一个"这样类似的要求
|
||
} else if (op[0] == 'Q') { //查询
|
||
scanf("%d", &x);
|
||
printf("%d\n", query(1, x)); //单点查询
|
||
} else { //恢复最近被摧毁位置的通道
|
||
modify(1, stk.top(), 1); //修改“前一个”位置的隧道值为1
|
||
stk.pop(); //堆栈弹出
|
||
}
|
||
}
|
||
}
|
||
return 0;
|
||
} |