bzoj1018 [SHOI2008]堵塞的交通

Description

　　有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个城市和3C-2条道路。小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：

　　Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了；Open r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了；Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N；

Input

　　第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于100000。

Output

　　对于每个查询，输出一个“Y”或“N”。

Sample Input

2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit

Sample Output

Y
N

HINT

题解：JudgeOnline/upload/201604/sol(4).rar

正解：线段树。

线段树神题，并且也是一个细节题。。

我们考虑使用线段树来维护两点的连通性，对于一个区间，维护$8$个参数。

$U$：区间$mid$和$mid+1$第$1$行的连通性。

$D$：区间$mid$和$mid+1$第$2$行的连通性。

$L$：区间左上，左下两点的连通性。

$R$：区间右上，右下两点的连通性。

$u$：区间左上，右上两点的连通性。

$d$：区间左下，右下两点的连通性。

$p$：区间左上，右下两点的连通性。

$q$：区间左下，右上两点的连通性。

标记合并的话，分类讨论一下，每种标记的连通都有两种走法。

然后就是查询了，我们考虑把$[c1,c2]$,$[1,c1]$,$[c2,c]$的标记弄出来，同时对于两点是否在同一行做$4$种讨论。

1.两点在$[c1,c2]$中直接连通，这个很简单。

2.两点通过$[1,c1]$的$R$和$[c1,c2]$中的一条边连通。

3.两点通过$[c2,c]$的$L$和$[c1,c2]$中的一条边连通。

4.两点通过$[1,c1]$的$R$和$[c2,c]$中的$L$和$[c1,c2]$中一条边连通，我就是因为这里漏判才错了好久。。

还有一点，注意查询时两区间合并一定要留住$U$,$D$两个标记！！

然后我们分类讨论一下就可以做出这题了，不过挺容易错的。。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define N (200010)
15 #define ls (x<<1)
16 #define rs (x<<1|1)
17 #define il inline
18 #define RG register
19 #define ll long long
20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
21 
22 using namespace std;
23 
24 struct data{ int U,D,L,R,u,d,p,q; }v[4*N];
25 
26 int c,r1,c1,r2,c2,fg;
27 char s[10];
28 
29 il int gi(){
30     RG int x=0,q=1; RG char ch=getchar();
31     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
32     if (ch=='-') q=-1,ch=getchar();
33     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
34     return q*x;
35 }
36 
37 il void merge(data &x,data l,data r){
38     x.u=(l.u&x.U&r.u)|(l.p&x.D&r.q),x.d=(l.d&x.D&r.d)|(l.q&x.U&r.p);
39     x.p=(l.u&x.U&r.p)|(l.p&x.D&r.d),x.q=(l.d&x.D&r.q)|(l.q&x.U&r.u);
40     x.L=l.L|(l.u&x.U&r.L&x.D&l.d),x.R=r.R|(r.u&x.U&l.R&x.D&r.d); return;
41 }
42 
43 il void build(RG int x,RG int l,RG int r){
44     if (l==r){ v[x].U=v[x].D=v[x].u=v[x].d=1; return; } RG int mid=(l+r)>>1;
45     build(ls,l,mid),build(rs,mid+1,r); return;
46 }
47 
48 il void update1(RG int x,RG int l,RG int r,RG int ps,RG int k){
49     if (l==r){ v[x].L=v[x].R=v[x].p=v[x].q=k; return; } RG int mid=(l+r)>>1;
50     (ps<=mid)?update1(ls,l,mid,ps,k):update1(rs,mid+1,r,ps,k); merge(v[x],v[ls],v[rs]); return;
51 }
52 
53 il void update2(RG int x,RG int l,RG int r,RG int c,RG int ps,RG int k){
54     RG int mid=(l+r)>>1; if (ps==mid){ (c==1)?v[x].U=k:v[x].D=k; merge(v[x],v[ls],v[rs]); return; }
55     (ps<=mid)?update2(ls,l,mid,c,ps,k):update2(rs,mid+1,r,c,ps,k); merge(v[x],v[ls],v[rs]); return;
56 }
57 
58 il data query(RG int x,RG int l,RG int r,RG int xl,RG int xr){
59     if (xl<=l && r<=xr) return v[x]; RG int mid=(l+r)>>1;
60     if (xr<=mid) return query(ls,l,mid,xl,xr);
61     else if (xl>mid) return query(rs,mid+1,r,xl,xr);
62     else{ RG data res=v[x]; merge(res,query(ls,l,mid,xl,mid),query(rs,mid+1,r,mid+1,xr)); return res; }
63 }
64 
65 il void work(){
66     c=gi(),build(1,1,c);
67     while (scanf("%s",s)!=EOF){
68     if (s[0]=='E') break;
69     r1=gi(),c1=gi(),r2=gi(),c2=gi(); if (c1>c2) swap(c1,c2),swap(r1,r2);
70     if (s[0]=='O') (c1==c2)?update1(1,1,c,c1,1):update2(1,1,c,r1,c1,1);
71     if (s[0]=='C') (c1==c2)?update1(1,1,c,c1,0):update2(1,1,c,r1,c1,0);
72     if (s[0]=='A'){
73         RG data res=query(1,1,c,c1,c2),res1=query(1,1,c,1,c1),res2=query(1,1,c,c2,c);
74         if (r1==1 && r2==1) fg=res.u|(res1.R&res.q)|(res2.L&res.p)|(res1.R&res.d&res2.L);
75         if (r1==2 && r2==2) fg=res.d|(res1.R&res.p)|(res2.L&res.q)|(res1.R&res.u&res2.L);
76         if (r1==1 && r2==2) fg=res.p|(res1.R&res.d)|(res.u&res2.L)|(res1.R&res.q&res2.L);
77         if (r1==2 && r2==1) fg=res.q|(res1.R&res.u)|(res.d&res2.L)|(res1.R&res.p&res2.L);
78         puts(fg ? "Y" : "N");
79     }
80     }
81     return;
82 }
83 
84 int main(){
85     File("traffic");
86     work();
87     return 0;
88 }