hdu1540 Tunnel Warfare

題意： 給定一個長度為 n n n的序列，初始所有元素都是 1 1 1。現在有三種操作：

D   x D \ x D x表示将 x x x位置的元素由1改成0， R R R表示将最近一次被修改成 0 0 0的元素改成改成 1 1 1， Q   x Q \ x Q x表示求得最長的全 1 1 1序列，其中序列必須包括第 x x x個位置。

題解： 經典單點修改，區間查詢。記錄每個區間的最長字首和最長字尾，然後判斷 x x x是否存在于左子區間的最長字尾中或是否存在于右子區間的最長字首中，再計算即可。注意要動态更新最近一次被修改為 0 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;
}