首页 > 代码库 > BZOJ 1018
BZOJ 1018
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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据，我们保证C小于等于1000，信息条数小于等于1000； 对100%测试数据，我们保证 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
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
N
HINT
Source
一道很恶心的数据结构题，但是数据结构却很简单，就是一颗裸的线段树。然而，用线段树维护连通性却很恶心（因为它只有相邻的两个点之间有连边）。我的线段树维护了8个域——左右，上下，对角，中间。慢慢写，反正我是写醉了。
奉劝：（代码仅限对拍，莫看莫看）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 6 #define maxn 100010 7 int n; 8 struct node 9 { 10 int lc,rc,l,r; 11 bool u[3]; //左上-左下 右上-右下 12 bool v[3]; //左上-右上 左下-右下 13 bool w[3]; //左下-右上 左上-右下 14 bool t[3]; //中间的两个 15 }; 16 struct SEG 17 { 18 int cnt; node tree[maxn*8]; 19 20 inline void updata(int now,bool flag) 21 { 22 tree[now].w[1] = tree[now].w[2] = false; 23 if (!flag) if (tree[now].l != tree[now].r) tree[now].u[1] = tree[now].u[2] = false,tree[now].v[1] = tree[now].v[2] = false; 24 int lc = tree[now].lc,rc = tree[now].rc; bool sign = false; 25 do 26 { 27 sign = false; 28 if (!tree[now].u[1]) 29 { 30 if (tree[now].v[1]&&tree[now].w[1]) 31 tree[now].u[1] = true,sign = true; 32 else if (tree[now].v[2]&&tree[now].w[2]) 33 tree[now].u[1] = true,sign = true; 34 else if (tree[now].u[2]&&tree[now].v[1]&&tree[now].v[2]) 35 tree[now].u[1] = true,sign = true; 36 else if (tree[lc].u[1]) tree[now].u[1] = true,sign = true; 37 } 38 if (!tree[now].u[2]) 39 { 40 if (tree[now].v[1]&&tree[now].w[2]) 41 tree[now].u[2] = true,sign = true; 42 else if (tree[now].v[2]&&tree[now].w[1]) 43 tree[now].u[2] = true,sign = true; 44 else if (tree[now].u[1]&&tree[now].v[1]&&tree[now].v[2]) 45 tree[now].u[2] = true,sign = true; 46 else if (tree[rc].u[2]) tree[now].u[2] = true,sign = true; 47 } 48 if (!tree[now].v[1]) 49 { 50 if (tree[now].r - tree[now].l == 1 && tree[now].t[1]) 51 tree[now].v[1] = true,sign = true; 52 else if (tree[now].u[1]&&tree[now].w[1]) 53 tree[now].v[1] = true,sign = true; 54 else if (tree[now].u[2]&&tree[now].w[2]) 55 tree[now].v[1] = true,sign = true; 56 else if (tree[lc].v[1]&&tree[rc].v[1]&&tree[now].t[1]) 57 tree[now].v[1] = true,sign = true; 58 else if (tree[lc].w[2]&&tree[now].t[2]&&tree[rc].w[1]) 59 tree[now].v[1] = true,sign = true; 60 } 61 if (!tree[now].v[2]) 62 { 63 if (tree[now].r - tree[now].l == 1 && tree[now].t[2]) 64 tree[now].v[2] = true,sign = true; 65 if (tree[now].u[1]&&tree[now].w[2]) 66 tree[now].v[2] = true,sign = true; 67 else if (tree[now].u[2]&&tree[now].w[1]) 68 tree[now].v[2] = true,sign = true; 69 else if (tree[lc].v[2]&&tree[rc].v[2]&&tree[now].t[2]) 70 tree[now].v[2] = true,sign = true; 71 else if (tree[lc].w[1]&&tree[now].t[1]&&tree[rc].w[2]) 72 tree[now].v[2] = true,sign = true; 73 } 74 if (!tree[now].w[1]) 75 { 76 if (tree[now].u[1]&&tree[now].v[1]) 77 tree[now].w[1] = true,sign = true; 78 else if (tree[now].u[2]&&tree[now].v[2]) 79 tree[now].w[1] = true,sign = true; 80 else if (tree[lc].w[1]&&tree[now].t[1]&&tree[rc].v[1]) 81 tree[now].w[1] = true,sign = true; 82 else if (tree[lc].v[2]&&tree[now].t[2]&&tree[now].w[1]) 83 tree[now].w[1] = true,sign = true; 84 } 85 if (!tree[now].w[2]) 86 { 87 if (tree[now].u[1]&&tree[now].v[2]) 88 tree[now].w[2] = true,sign = true; 89 else if (tree[now].u[2]&&tree[now].v[1]) 90 tree[now].w[2] = true,sign = true; 91 else if (tree[lc].w[2]&&tree[now].t[2]&&tree[rc].v[2]) 92 tree[now].w[2] = true,sign = true; 93 else if (tree[lc].v[1]&&tree[now].t[1]&&tree[rc].w[2]) 94 tree[now].w[2] = true,sign = true; 95 } 96 } 97 while (sign); 98 if (tree[now].l == tree[now].r) 99 tree[now].w[1] = tree[now].w[2] = false;100 }101 102 inline int build(int l,int r)103 {104 int now = ++cnt,mid = (l + r) >> 1;105 tree[now].l = l; tree[now].r = r;106 if (l == r)107 {108 tree[now].v[1] = tree[now].v[2] = true;109 updata(now,1);110 return now;111 }112 tree[now].lc = build(l,mid);113 tree[now].rc = build(mid+1,r);114 updata(now,1);115 return now;116 }117 118 inline bool ask(int a1,int b1,int a2,int b2,int now)119 {120 if (a1 == a2 && b1 == b2) return true;121 int l = tree[now].l,r = tree[now].r,lc = tree[now].lc,rc = tree[now].rc,mid = (l + r) >> 1;122 if (b1 == l&&b2 == r)123 {124 if (a1 == a2 && tree[now].v[a1]) return true;125 if (a1 != a2)126 {127 if (a1 == 1 && tree[now].w[2]) return true;128 if (a1 == 2 && tree[now].w[1]) return true;129 if (l == r && tree[now].u[1]) return true; 130 }131 }132 else if (b2 <= mid && ask(a1,b1,a2,b2,lc)) return true;133 else if (b1 > mid && ask(a1,b1,a2,b2,rc)) return true;134 else if (mid >= b1 && mid < b2 && tree[now].t[1]&&ask(a1,b1,1,mid,lc)&&ask(1,mid+1,a2,b2,rc)) return true;135 else if (mid >= b1 && mid < b2 && tree[now].t[2]&&ask(a1,b1,2,mid,lc)&&ask(2,mid+1,a2,b2,rc)) return true;136 else if (a1 != a2 && tree[now].t[1] && tree[now].t[2])137 {138 if (b2 <= mid) return tree[rc].u[1]&&ask(a1,b1,a1,mid,lc)&&ask(a2,b2,a2,mid,lc);139 else if (b1 > mid) return tree[lc].u[2]&&ask(a1,mid+1,a1,b1,rc)&&ask(a2,mid+1,a2,b2,rc);140 }141 else if (a1 == a2 && tree[now].t[1]&&tree[now].t[2])142 {143 if (b2 <= mid)144 return tree[rc].u[1]&&ask(a1,b1,((a1-1)^1)+1,b1,lc)&&ask(((a1-1)^1)+1,b1,((a1-1)^1)+1,mid,lc)&&ask(a2,b2,a2,mid,lc);145 else if (b1 > mid)146 return tree[lc].u[2]&&ask(a1,b2,((a1-1)^1)+1,b2,rc)&&ask(((a1-1)^1)+1,mid+1,((a1-1)^1)+1,b2,rc)&&ask(a2,mid+1,a2,b1,rc);147 }148 return false;149 }150 151 inline void modify(int a1,int b1,int a2,int b2,int now,bool sign)152 {153 int l = tree[now].l,r = tree[now].r,lc = tree[now].lc,rc = tree[now].rc,mid = (l + r) >> 1;154 bool flag = false;155 if (a1 == a2) //处在同一行上156 {157 if (b1 == mid && b2 == mid + 1)158 tree[now].t[a1] = sign,flag = sign;159 else if (b1 <= mid) modify(a1,b1,a2,b2,lc,sign);160 else modify(a1,b1,a2,b2,rc,sign);161 }162 else //处在同一列上163 {164 if (l == r) tree[now].u[1] = tree[now].u[2] = sign,flag = true;165 else if (b1 <= mid) modify(a1,b1,a2,b2,lc,sign);166 else modify(a1,b1,a2,b2,rc,sign);167 }168 updata(now,flag|sign);169 return;170 } 171 }seg;172 173 inline int read()174 {175 int x=0,f=1; char ch=getchar();176 while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘)f=-1; ch=getchar(); }177 while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); }178 return x * f;179 }180 181 int main()182 {183 freopen("1018.in","r",stdin);184 freopen("1018.out","w",stdout);185 n = read();186 seg.build(1,n);187 char opt[10]; int a1,a2,b1,b2;188 do189 {190 scanf("%s ",opt); 191 if (opt[0] == ‘E‘) break;192 a1 = read(); b1 = read(); a2 = read(); b2 = read();193 if (b1 > b2) swap(a1,a2),swap(b1,b2);194 if (opt[0] == ‘A‘)195 {196 if (seg.ask(a1,b1,a2,b2,1)) printf("Y\n");197 else printf("N\n");198 }199 else if (opt[0] == ‘O‘) seg.modify(a1,b1,a2,b2,1,true);200 else seg.modify(a1,b1,a2,b2,1,false); 201 }202 while (true);203 return 0;204 }
BZOJ 1018
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。