BZOJ 1018 堵塞的交通

发表于 | 更新于

Link

Solution

线段树维护这几种可能性：

Tips

做过道路修建之后觉得这个很水。随便一写，WA。 于是找到数据，发现把Y的判成了N。 脑子一转，发现这道题和那道还不一样：这道的答案也有可能来自一端出去再回来。 于是改，WA。发现把N判成了Y。 看看代码，发现合并信息的时候少写了一个条件。 于是改，WA。发现把Y判成了N。 脑子一转，发现答案可能来自两端同时转出去再转回来。 于是改，AC。汗。。 细节问题一定要想好。。 细节多的题一定要对拍。。 对拍的时候一定要KISS，以覆盖到各种情况。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10;
using std::swap;
struct Data
{
	int a[2][2],tor[2],sf[2];
	int *operator [](int x){return a[x];}
	Data(){memset(a,0,sizeof(a));tor[0]=tor[1]=sf[0]=sf[1]=0;}
};
Data Merge(Data a,Data b)
{
	Data res;
	res[0][0]=(a[0][0]&b[0][0]&a.tor[0]) | (a[0][1]&b[1][0]&a.tor[1]);
	res[1][0]=(a[1][0]&b[0][0]&a.tor[0]) | (a[1][1]&b[1][0]&a.tor[1]);
	res[0][1]=(a[0][0]&b[0][1]&a.tor[0]) | (a[0][1]&b[1][1]&a.tor[1]);
	res[1][1]=(a[1][0]&b[0][1]&a.tor[0]) | (a[1][1]&b[1][1]&a.tor[1]);
	res.tor[0]=b.tor[0],res.tor[1]=b.tor[1];
	res.sf[0]=a.sf[0] | (b.sf[0] & a[0][0] & a.tor[0] & a[1][1] & a.tor[1]);
	res.sf[1]=b.sf[1] | (a.sf[1] & b[0][0] & a.tor[0] & b[1][1] & a.tor[1]);
	return res;
}
namespace iSeg
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		Node *son[2];
		Data v;
		void up(){v=Merge(son[0]->v,son[1]->v);}
		Node(){son[0]=son[1]=0;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null;
	Node *newNode()
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;
		return cur;
	}
	void Build(Node *&pos,int L,int R)
	{
		pos=newNode();
		if(L==R)
			 pos->v[0][0]=pos->v[1][1]=1;
		else
		{
			int MID=(L+R)>>1;
			Build(pos->son[0],L,MID);
			Build(pos->son[1],MID+1,R);
			pos->up();
		}
	}
	Data Access(Node *pos,int L,int R,int l,int r)
	{
		if(L==l && R==r) return pos->v;
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID) return Access(pos->son[0],L,MID,l,r);
			else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
			else return Merge(Access(pos->son[0],L,MID,l,MID),Access(pos->son[1],MID+1,R,MID+1,r));
		}
	}
	void Edit(Node *pos,int L,int R,int x1,int x2,int y1,int y2,int d)
	{
		if(L==R)
		{
			if(y1==y2) pos->v[0][1]=pos->v[1][0]=pos->v.sf[0]=pos->v.sf[1]=d;
			else pos->v.tor[x1]=d;
		}
		else
		{
			int MID=(L+R)>>1;
			if(y1<=MID) Edit(pos->son[0],L,MID,x1,x2,y1,y2,d);
			else Edit(pos->son[1],MID+1,R,x1,x2,y1,y2,d);
			pos->up();
		}
	}
}using namespace iSeg;
int main()
{
	int n;get(n);
	Build(root,1,n);
	char opt[10];int x1,y1,x2,y2,lc,rc;Data res;
	while(scanf("%s",opt),opt[0]!='E')
	{
		get(x1),get(y1),get(x2),get(y2);
		x1--,x2--;
		if(y1>y2 || (y1==y2 && x1>x2)) swap(x1,x2),swap(y1,y2);
		switch(opt[0])
		{
			case 'A':
				//static int cnt;if(++cnt==91) puts("");
				res=Access(root,1,n,y1,y2);
				lc=Access(root,1,n,1,y1).sf[1];
				rc=Access(root,1,n,y2,n).sf[0];
				puts(res[x1][x2] || (lc && res[x1^1][x2]) || (rc && res[x1][x2^1]) || (lc && rc && res[x1^1][x2^1])?"Y":"N");
				break;
			case 'O':Edit(root,1,n,x1,x2,y1,y2,1);break;
			case 'C':Edit(root,1,n,x1,x2,y1,y2,0);break;
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */