HDU-1540 Tunnel warfare

维护每个区间左端点 能向右走到的最大距离，右端点能向左走到的最大距离

查询的时候，如果当前查询的节点在左子树的rmax里面话，就返回相应的反正继续递归

若位于右子树的话同理可以得到结果

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct Segment{
	int l,r;
	int lmax,rmax;
}tr[N<<2];
int n,m;


void pushup(int u){
	Segment &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
	root.lmax = left.lmax + (left.lmax == left.r-left.l+1?right.lmax:0);
	root.rmax = right.rmax + (right.rmax == right.r-right.l+1?left.rmax:0);
}


void build(int u,int l,int r){
	tr[u] = {l,r,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);
}

void modify(int u,int x,int c){
	if(tr[u].l==x && tr[u].r==x){
		tr[u].lmax = tr[u].rmax = c;
		return;
	}
	
	int mid = tr[u].l+tr[u].r>>1;
	if(x<=mid)modify(u<<1,x,c);
	if(x>mid)modify(u<<1|1,x,c);
	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;
	
	if(x<=mid){
		if(x>=tr[u<<1].r-tr[u<<1].rmax+1)
		 return tr[u<<1].rmax + tr[u<<1|1].lmax;
		
		return query(u<<1,x);
	}
	
	else{
		if(x<=tr[u<<1|1].l+tr[u<<1|1].lmax-1)
		 return tr[u<<1|1].lmax + tr[u<<1].rmax;
		
		return query(u<<1|1,x);
	}
	
	
	
}



int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	while(cin>>n>>m){
		build(1,1,n);
		//cout<<query(1,n)<<"\n";
		char c;int x;
		stack<int>st;
		while(m--){
			cin>>c;
			if(c=='D'){cin>>x;modify(1,x,0);st.push(x);}
			else if(c=='R'){
				if(st.size()){
					int t = st.top();
					st.pop();
					modify(1,t,1);
				}
				
			}
			else {cin>>x;cout<<query(1,x)<<"\n";}
		}
		
	}
}