[BZOJ 1018] [SHOI2008] 堵塞的交通traffic 【线段树维护联通性】

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

inline int gmin(int a, int b) {return a < b ? a : b;}
inline int gmax(int a, int b) {return a > b ? a : b;}

const int MaxN = 100000 + 5;

int n;

char Str[15];

bool A[MaxN][3];

struct ES
{
	bool a1, a2, b1, b2, c1, c2;
} T[MaxN * 4]; 

inline ES Plus(ES e1, ES e2, int m)
{
	ES ret;
	ret.a1 = e1.a1 || (e1.b1 && e1.b2 && A[m][1] && A[m][2] && e2.a1);
	ret.a2 = e2.a2 || (e2.b1 && e2.b2 && A[m][1] && A[m][2] && e1.a2);
	ret.b1 = (e1.b1 && A[m][1] && e2.b1) || (e1.c1 && A[m][2] && e2.c2);
	ret.b2 = (e1.b2 && A[m][2] && e2.b2) || (e1.c2 && A[m][1] && e2.c1);
	ret.c1 = (e1.b1 && A[m][1] && e2.c1) || (e1.c1 && A[m][2] && e2.b2);
	ret.c2 = (e1.b2 && A[m][2] && e2.c2) || (e1.c2 && A[m][1] && e2.b1);
	return ret;
}

void Build(int x, int s, int t)
{
	if (s == t)
	{
		T[x].a1 = T[x].a2 = T[x].c1 = T[x].c2 = false;
		T[x].b1 = T[x].b2 = true;
		return;
	}
	int m = (s + t) >> 1;
	Build(x << 1, s, m);
	Build(x << 1 | 1, m + 1, t);
	T[x] = Plus(T[x << 1], T[x << 1 | 1], m);
}

void Modify(int x, int s, int t, int Pos)
{
	if (s == t)
	{
		T[x].a1 = T[x].a2 = T[x].c1 = T[x].c2 = A[Pos][0];
		T[x].b1 = T[x].b2 = true;
		return;
	}
	int m = (s + t) >> 1;
	if (Pos <= m) Modify(x << 1, s, m, Pos);
	else Modify(x << 1 | 1, m + 1, t, Pos);
	T[x] = Plus(T[x << 1], T[x << 1 | 1], m);
}

ES Get(int x, int s, int t, int l, int r)
{
	if (l <= s && r >= t) return T[x];
	ES ret;
	int m = (s + t) >> 1;
	if (r <= m) ret = Get(x << 1, s, m, l, r);
	else if (l >= m + 1) ret = Get(x << 1 | 1, m + 1, t, l, r);
	else ret = Plus(Get(x << 1, s, m, l, r), Get(x << 1 | 1, m + 1, t, l, r), m);
	return ret;
}

int main()
{
	scanf("%d", &n);
	int x, y, xx, yy;
	bool f, Ans;
	ES El, Ex, Er;
	Build(1, 1, n);
	while (true)
	{
		scanf("%s", Str);
		if (strcmp(Str, "Exit") == 0) break;
		scanf("%d%d%d%d", &x, &y, &xx, &yy);
		if (strcmp(Str, "Ask") == 0)
		{
			if (y > yy) 
			{
				swap(x, xx);
				swap(y, yy);
			}
			El = Get(1, 1, n, 1, y);
			Ex = Get(1, 1, n, y, yy);
			Er = Get(1, 1, n, yy, n);
			if (x == xx)
			{
				if (x == 1) 
					Ans = Ex.b1 || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && Ex.c2) || 					(A[yy][1] && A[yy][2] && Er.a1 && Ex.c1) || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && A[yy][1] && A[yy][2] && Er.a1 && Ex.b2);
				else 
					Ans = Ex.b2 || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && Ex.c1) || 					(A[yy][1] && A[yy][2] && Er.a1 && Ex.c2) || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && A[yy][1] && A[yy][2] && Er.a1 && Ex.b1);
			}
			else
			{
				if (x < xx)
					Ans = Ex.c1 || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && Ex.b2) || 					(Ex.b1 && A[yy][1] && A[yy][2] && Er.a1);
				else 
					Ans = Ex.c2 || 					(A[y - 1][1] && A[y - 1][2] && El.a2 && Ex.b1) || 					(Ex.b2 && A[yy][1] && A[yy][2] && Er.a1);
			}
			if (Ans) printf("Y\n");
			else printf("N\n");	
		}
		else
		{
			if (strcmp(Str, "Open") == 0) f = true;
			else f = false;
			if (x == xx) 
			{	
				A[gmin(y, yy)][x] = f;
				Modify(1, 1, n, gmin(y, yy));
			}
			else
			{
				A[y][0] = f;
				Modify(1, 1, n, y);
			}
		}
	}
	return 0;
}