bzoj1018: [SHOI2008]堵塞的交通traffic 线段树

#include<bits/stdc++.h>
#define N 100005
#define M (l+r>>1)
#define P (k<<1)
#define S (k<<1|1)
#define K l,r,k
#define L l,M,P
#define R M+1,r,S
#define Z int l=1,int r=n,int k=1
using namespace std;
int n,m;
struct node{
	bool u[2],v[2],a[2];
}a[1<<18];
bool t[2][N];
node merge(node u,node v,Z){
	node s[]={u,v},a;
	for(int i=0;i!=2;++i){
		a.u[i]=s[0].u[i]&&t[i][M]
		&&s[1].u[i]||s[0].a[i]
		&&t[i^1][M]&&s[1].a[i^1];
		a.v[i]=s[i].v[i]||t[0][M]
		&&s[i].u[0]&&s[i].u[1]
		&&t[1][M]&&s[i^1].v[i];
		a.a[i]=s[0].u[i]&&t[i][M]
		&&s[1].a[i]||s[0].a[i]
		&&t[i^1][M]&&s[1].u[i^1];
	}
	return a;
}
node Q(int s,int t,Z){
	return s==l&&t==r?a[k]
	:t<=M?Q(s,t,L)
	:s>M?Q(s,t,R)
	:merge(Q(s,M,L),
	Q(M+1,t,R),K);
}
bool solve(int s,int t,int i,int j){
	node a=Q(s,t);
	node u=Q(1,s),v=Q(t,n);
	return i==j?
	u.v[1]&&a.u[i^1]&&v.v[0]
	||a.u[i]:a.u[j]&&u.v[1]
	||a.u[i]&&v.v[0]||a.a[i]
	||u.v[1]&&v.v[0]&&a.a[j];
}
void build(Z){
	if(l==r)
		memset(a[k].u,1,2);
	else{
		build(L);
		build(R);
	}
}
void update(Z){
	a[k]=merge(a[P],a[S],K);
}
void F(int t,Z){
	return l==r?void()
	:(t<=M?F(t,L)
	:F(t,R),update(K));
}
void G(int s,int t,Z){
	if(l==r){
		memset(a[k].v,s,2);
		memset(a[k].a,s,2);
	}else{
		if(t<=M)
			G(s,t,L);
		else
			G(s,t,R);
		update(K);
	}
}
int main(){
	scanf("%d",&n);
	build();
	char s[8];
	while(scanf("%s",s),*s!=‘E‘){
		int u,v,i,j;
		scanf("%d%d%d%d",&i,&u,&j,&v);
		--i,--j;
		if(u>v){
			swap(u,v);
			swap(i,j);
		}
		if(*s==‘A‘)
			puts(solve(
			u,v,i,j)?"Y":"N");
		else{
			bool z=*s==‘O‘;
			i!=j?G(z,u)
			:(t[i][u]=z,F(u));
		}
	}
}