题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1018将地图中的格子作为节点，用线段树维护每个区间左上、左下、右上、右下间的关系。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;
const int MaxC=100050;
struct node
{
bool lu_ld,lu_ru,ru_rd,ld_rd,lu_rd,ld_ru,road1,road2,road3,road4;
/**//*{
lu_ld=1;//1
lu_ru=1;//2
ru_rd=1;//3
ld_rd=1;//4
lu_rd=1;
ld_ru=1;
}*/
};
int c;
node t[2*MaxC];
void pay(node &t)
{
t.lu_ld=1;//1
t.lu_ru=1;//2
t.ru_rd=1;//3
t.ld_rd=1;//4
t.lu_rd=1;
t.ld_ru=1;
}
void merge(node &tt,node t1,node t2)
{
tt.lu_ld=(t1.lu_ld) || (t1.lu_ru && t1.ld_rd && t2.lu_ld);
tt.ru_rd=(t2.ru_rd) || (t2.lu_ru && t2.ld_rd && t1.ru_rd);
tt.lu_ru=(t1.lu_ru && t2.lu_ru) || (t1.lu_rd && t2.ld_ru);
tt.ld_rd=(t1.ld_rd && t2.ld_rd) || (t1.ld_ru && t2.lu_rd);
tt.lu_rd=(tt.lu_ld && tt.ld_rd) || (tt.lu_ru && tt.ru_rd) ||
(t1.lu_rd && t2.ld_rd) || (t1.lu_ru && t2.lu_rd);
tt.ld_ru=(tt.ru_rd && tt.ld_rd) || (tt.lu_ru && tt.lu_ld) ||
(t1.ld_ru && t2.lu_ru) || (t1.ld_rd && t2.ld_ru);
}
void empty(node &t)
{
t.lu_ld=0;
t.lu_ru=0;
t.ru_rd=0;
t.ld_rd=0;
t.lu_rd=0;
t.ld_ru=0;
}
void build(int x,int left,int right)
{
pay(t[x]);
if (left!=right)
{
int mid=(left+right)>>1;
build(2*x,left,mid);
build(2*x,mid+1,right);
}
}
void change(int x,int left,int right,int v,int kind,int value)
{
//cout<<left<<' '<<right<<endl;
if (left==right)
{
switch (kind)
{
case 1:
t[x].road1=value;
break;
case 2:
t[x].road2=value;
break;
case 3:
t[x].road3=value;
break;
case 4:
t[x].road4=value;
break;
}
t[x].lu_ld=t[x].road1 || (t[x].road2 && t[x].road4 && t[x].road3);
t[x].lu_ru=t[x].road2 || (t[x].road1 && t[x].road4 && t[x].road3);
t[x].ru_rd=t[x].road3 || (t[x].road2 && t[x].road4 && t[x].road1);
t[x].ld_rd=t[x].road4 || (t[x].road2 && t[x].road1 && t[x].road3);
t[x].lu_rd=(t[x].lu_ld && t[x].ld_rd) || (t[x].lu_ru && t[x].ru_rd);
t[x].ld_ru=(t[x].ru_rd && t[x].ld_rd) || (t[x].lu_ru && t[x].lu_ld);
return;
}
int mid=(left+right)>>1;
if (v<=mid)
{
change(2*x,left,mid,v,kind,value);
}
else
{
change(2*x+1,mid+1,right,v,kind,value);
}
merge(t[x],t[2*x],t[2*x+1]);
}
node get(int x,int left,int right,int vleft,int vright)
{
if (left==vleft && right==vright)
{
return t[x];
}
int mid=(left+right)>>1;
if (vright<=mid)
{
return get(2*x,left,mid,vleft,vright);
}
if (vleft>=mid+1)
{
return get(2*x+1,mid+1,right,vleft,vright);
}
node t1=get(2*x,left,mid,vleft,mid),t2=get(2*x+1,mid+1,right,mid+1,vright),tt;
merge(tt,t1,t2);
return tt;
}
int main()
{
//freopen("1018.txt","r",stdin);
//freopen("out1.txt","w",stdout);
char s[10];
scanf(" %d",&c);
scanf(" %s",&s);
//build(1,1,c-1);
while (strcmp(s,"Exit")!=0)
{
//cout<<s<<endl;
int a,b,d,e;
scanf("%d%d%d%d",&a,&b,&d,&e);
if (b>e)
{
int t1=b,t2=a;
b=e;
a=d;
e=t1;
d=t2;
}
if (strcmp(s,"Open")==0)
{
if (b==e)
{
if (b-1>0)
{
change(1,1,c-1,b-1,3,1);
}
if (b<=c-1)
{
change(1,1,c-1,b,1,1);
}
}
else
{
if (a==1)
{
change(1,1,c-1,b,2,1);
}
else
{
change(1,1,c-1,b,4,1);
}
}
}
if (strcmp(s,"Close")==0)
{
if (b==e)
{
if (b-1>0)
{
change(1,1,c-1,b-1,3,0);
}
if (b<=c-1)
{
change(1,1,c-1,b,1,0);
}
}
else
{
if (a==1)
{
change(1,1,c-1,b,2,0);
}
else
{
change(1,1,c-1,b,4,0);
}
}
}
if (strcmp(s,"Ask")==0)
{
if (a==d && b==e)
{
printf("Y\n");
scanf(" %s",&s);
continue;
}
node t1,t2,t3;
if (b<=e-1)
{
t2=get(1,1,c-1,b,e-1);
}
else
{
empty(t2);
}
if (1<=b-1)
{
t1=get(1,1,c-1,1,b-1);
}
else
{
empty(t1);
}
if (e<=c-1)
{
t3=get(1,1,c-1,e,c-1);
}
else
{
empty(t3);
}
if (a==d)
{
if (a==1)
{
switch (t2.lu_ru || (t1.ru_rd && t2.ld_rd && t3.lu_ld))
{
case 1:
printf("Y\n");
break;
case 0:
printf("N\n");
break;
}
}
else
{
switch (t2.ld_rd || (t1.ru_rd && t2.lu_ru && t3.lu_ld))
{
case 1:
printf("Y\n");
break;
case 0:
printf("N\n");
break;
}
}
}
else
{
if (b==e)
{
switch (t1.ru_rd || t3.lu_ld)
{
case 1:
printf("Y\n");
break;
case 0:
printf("N\n");
break;
}
}
else
{
if (a==1)
{
switch (t2.lu_rd || (t1.ru_rd && t2.ld_rd) || (t2.lu_ru && t3.lu_ld))
{
case 1:
printf("Y\n");
break;
case 0:
printf("N\n");
break;
}
}
else
{
switch (t2.ld_ru || (t1.ru_rd && t2.lu_ru) || (t2.ld_rd && t3.lu_ld))
{
case 1:
printf("Y\n");
break;
case 0:
printf("N\n");
break;
}
}
}
}
}
scanf(" %s",&s);
}
return 0;
}