西宁做网站/友情链接查询工具

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

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

Sample Output

YN

HINT

Source

图很丑，我就这么标了一下号…

线段树维护四个节点两两是否联通，一共六个东西。
然后原图中的标号和线段树中的标号不一样，线段树每个节点维护四个原图中的节点，这样合并的时候好合并，见右下角。

然后对于单点修改，记录原图中的边，然后修改时跑floyd就行了…

因为标号不同要特判横着还是竖着，要特判竖着的是否在边界，因为有可能绕圈所以要特判左边绕、右边绕、都绕的情况……总之挺恶心的

思路很好想，代码好恶心…大概是我写傻了……

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;const int SZ = 200010;struct segment{int l,r;bool c[10]; 
}tree[SZ << 2];void update(segment &p,segment lch,segment rch)
{p.c[1] = ( lch.c[1] | (lch.c[2]  &  lch.c[4] & rch.c[1])); p.c[2] = ((lch.c[2] &  rch.c[2]) | (lch.c[6] & rch.c[5])); p.c[3] = ( rch.c[3] | (rch.c[2]  &  rch.c[4] & lch.c[3]));p.c[4] = ((lch.c[4] &  rch.c[4]) | (lch.c[5] & rch.c[6]));p.c[5] = ((lch.c[4] &  rch.c[5]) | (lch.c[5] & rch.c[2]));p.c[6] = ((lch.c[6] &  rch.c[4]) | (lch.c[2] & rch.c[6]));
}void build(int p,int l,int r)
{tree[p].l = l; tree[p].r = r;if(l == r)return ;int mid = l + r >> 1;build(p << 1,l,mid); build(p << 1 | 1,mid + 1,r);update(tree[p],tree[p << 1],tree[p << 1 | 1]);
}bool maps[SZ][5][5];
bool floyd[SZ][5][5];void modify(int p,int pos,int x,int d)
{
/*  maps[pos][0][2] = maps[pos][2][0] = tree[p].c[1];maps[pos][0][1] = maps[pos][1][0] = tree[p].c[2];maps[pos][1][3] = maps[pos][3][1] = tree[p].c[3];maps[pos][3][2] = maps[pos][2][3] = tree[p].c[4];maps[pos][1][2] = maps[pos][2][1] = tree[p].c[5];maps[pos][0][3] = maps[pos][3][0] = tree[p].c[6];*/if(x == 1) maps[pos][0][2] = maps[pos][2][0] = d;if(x == 2) maps[pos][0][1] = maps[pos][1][0] = d;if(x == 3) maps[pos][1][3] = maps[pos][3][1] = d;if(x == 4) maps[pos][3][2] = maps[pos][2][3] = d;if(x == 5) maps[pos][1][2] = maps[pos][2][1] = d;if(x == 6) maps[pos][0][3] = maps[pos][3][0] = d;for(int i = 0;i < 4;i ++)for(int j = 0;j < 4;j ++)floyd[pos][i][j] = maps[pos][i][j]; for(int k = 0;k < 4;k ++)for(int i = 0;i < 4;i ++)for(int j = 0;j < 4;j ++)floyd[pos][i][j] |= floyd[pos][i][k] & floyd[pos][k][j]; tree[p].c[1] = floyd[pos][0][2];tree[p].c[2] = floyd[pos][0][1];tree[p].c[3] = floyd[pos][3][1];tree[p].c[4] = floyd[pos][2][3];tree[p].c[5] = floyd[pos][2][1];tree[p].c[6] = floyd[pos][0][3];
}void change(int p,int pos,int x,int d)
{if(tree[p].l == tree[p].r){modify(p,pos,x,d);return;}int mid = tree[p].l + tree[p].r >> 1;if(pos <= mid) change(p << 1,pos,x,d);else change(p << 1 | 1,pos,x,d);update(tree[p],tree[p << 1],tree[p << 1 | 1]);
}segment find(int p,int l,int r)
{if(tree[p].l == l && r == tree[p].r)return tree[p];int mid = tree[p].l + tree[p].r >> 1;if(r <= mid) return find(p << 1,l,r);else if(l > mid) return find(p << 1 | 1,l,r);else{segment a = find(p << 1,l,mid);segment b = find(p << 1 | 1,mid + 1,r);segment c;update(c,a,b);  return c;}
}bool ask(int p,int l,int r,int x,int y)
{segment ans = find(1,l,r);
//  printf("%d %d\n",l,r);
//  for(int i = 1;i <= 6;i ++)
//      printf("%d ",ans.c[i]); puts(""); if(x > y) swap(x,y);if(x == 0 && y == 1) return ans.c[2]; if(x == 0 && y == 2) return ans.c[1]; if(x == 0 && y == 3) return ans.c[6]; if(x == 1 && y == 2) return ans.c[5]; if(x == 1 && y == 3) return ans.c[3]; if(x == 2 && y == 3) return ans.c[4]; 
}int rev[10],n;bool check(int r1,int c1,int r2,int c2)
{if(c1 > c2) swap(c1,c2),swap(r1,r2);int pl,pr;if(r1 == 1) pl = 0;else pl = 2;if(r2 == 1) pr = 1;else pr = 3;if(c1 == c2){if(c1 != n && ask(1,c1,n - 1,0,2)) return true;if(c1 != 1 && ask(1,1,c1 - 1,1,3)) return true;}else{if(ask(1,c1,c2 - 1,pl,pr)) return true;bool a = 0,b = 0;if(c1 != 1 && (a = ask(1,1,c1 - 1,1,3)) && ask(1,c1,c2 - 1,rev[pl],pr)) return true;if(c2 != n && (b = ask(1,c2,n - 1,0,2)) && ask(1,c1,c2 - 1,pl,rev[pr])) return true;if(c1 != 1 && c2 != n && a && b && ask(1,c1,c2 - 1,rev[pl],rev[pr])) return true;}return false;
}int main()
{rev[0] = 2; rev[2] = 0;rev[1] = 3; rev[3] = 1;scanf("%d",&n);build(1,1,n);char opt[10];while(~scanf("%s",opt) && opt[0] != 'E'){int r1,c1,r2,c2;scanf("%d%d%d%d",&r1,&c1,&r2,&c2);if(c1 > c2) swap(c1,c2),swap(r1,r2);if(opt[0] == 'O'){if(r1 == r2){if(r1 == 1)change(1,c1,2,1);elsechange(1,c1,4,1);}else{if(c1 != n)change(1,c1,1,1);if(c1 != 1)change(1,c1 - 1,3,1);}}else if(opt[0] == 'C'){if(r1 == r2){if(r1 == 1)change(1,c1,2,0);elsechange(1,c1,4,0);}else{if(c1 != n)change(1,c1,1,0);if(c1 != 1)change(1,c1 - 1,3,0);}} else{if(check(r1,c1,r2,c2)) puts("Y");else puts("N");}}return 0;
}
/**/