hdu1540 Tunnel Warfare

题意： 给定一个长度为 $n$n的序列，初始所有元素都是 $1$1。现在有三种操作：
$Dx$D x表示将 $x$x位置的元素由1改成0， $R$R表示将最近一次被修改成 $0$0的元素改成改成 $1$1， $Qx$Q x表示求得最长的全 $1$1序列，其中序列必须包括第 $x$x个位置。

题解： 经典单点修改，区间查询。记录每个区间的最长前缀和最长后缀，然后判断 $x$x是否存在于左子区间的最长后缀中或是否存在于右子区间的最长前缀中，再计算即可。注意要动态更新最近一次被修改为 $0$0的位置。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int latest[N], last, x;
char op[2];

struct Node{
	int l, r;
	int pre, suf, len;
}tr[N << 2];

void pushup(int u) {
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	root.pre = left.pre;
	if(left.pre == left.len) root.pre += right.pre;
	root.suf = right.suf;
	if(right.suf == right.len) root.suf += left.suf;
}

void build(int u, int l, int r) {
	tr[u] = {l, r, 1, 1, 1};
	if(l == r) return ;
	
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
	tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void modify(int u, int x, int c) {
	if(tr[u].len == 1) {
		tr[u].pre = tr[u].suf = c;
		return ;
	} 
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) modify(u << 1, x, c);
	else modify(u << 1 | 1, x, c);
	pushup(u);
}

int query(int u, int x) {
	
	if(tr[u].len == 1) return tr[u].pre;
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) {
		if(x >= tr[u << 1].r - tr[u << 1].suf + 1) 
			return tr[u << 1].suf + tr[u << 1 | 1].pre;
		else return query(u << 1, x);
	}
	else {
		if(x <= tr[u << 1 | 1].l + tr[u << 1 | 1].pre - 1)
			return tr[u << 1].suf + tr[u << 1 | 1].pre;
		else return query(u << 1 | 1, x);
	}
}

int main()
{
	while(~scanf("%d%d", &n, &m)) {
		last = 0;
		build(1, 1, n);
		
		while(m--) {
			scanf("%s", op);
			switch (op[0]) {
				case 'D' : 
					scanf("%d", &x);
					modify(1, x, 0);
					latest[x] = last;
					last = x;
					break;
				case 'R' :
					modify(1, last, 1);
					last = latest[last];
					break;
				case 'Q' :
					scanf("%d", &x);
					printf("%d\n", query(1, x));
					break;
			}
		}
	}
	
	return 0;
}