过程曲折,,,
- /**************************************************************
- Problem: 1018
- User: lxy8584099
- Language: C++
- Result: Accepted
- Time:1156 ms
- Memory:21928 kb
- ****************************************************************/
- /*
- 题意有点隐晦难懂
- 其实就是把以前用 第 k 个城市 的表示方法
- 改成了 第 i 行第 j 列的城市 的表示方法...
- 注: ri 表示行数, ci 表示列数 (from luogu
- 动态树仅能表示出一个点到另一个点的 一 条路线
- 此题不适用
- 改用线段树的区间维护
- 存在 b[x][i] 表示节点 x 的左儿子右儿子是否联通
- i=0 是第一行的左右是否联通 i=1 是第二行的左右是否联通
- 对于数的每一个节点 有以下内容
- 1. vis1[i][j] 表示该区间内的
- 第 i 行最左边能否到达第 j 行的最右边 4 个匹配关系 情况是 0/1
- 2.vis2[i]
- i=0 时 表示区间内最左边 能不能从他的右边 (不能超出该节点区间)
- 走到它所在行的另一行的同一位置 因为这是可逆的并且只有两行
- 所以不用说是第 i 行走到第 j 行
- i=1 时 表示区间内最右边 能不能从他的左边 (不能超出该节点区间)
- 走到它所在行的另一行的同一位置 同上
- 对于查询 要考虑路线走出这个区间的情况
- 所以分成三部分 1~y1 y1~y2 y2~n;
- 只要存在 中间能联通 || 走左变换行后能联通 || 走右边换行后能联通
- 就是联通的
- 码量有点大...
- 不抄博客绝对写不出来...
- 线段树节点概括的区间最好用数组存起来 函数中变量多了容易错误
- */
- #include<cstdio>
- #define lc (rt<<1)
- #define rc (rt<<1|1)
- #define mid ((l+r)>>1)
- using namespace std;
- const int N=8e5+50;
- int n; char str[10];
- struct traffic
- {
- struct line_tree
- {
- bool vis1[3][3],vis2[3];
- } f[N];
- bool b[N][3];
- int l[N],r[N],m[N];
- line_tree merge(line_tree f0,line_tree f1,bool b[])
- {
- line_tree res;
- for(int i=0;i<2;i++)
- for(int j=0;j<2;j++)
- res.vis1[i][j]=(f0.vis1[i][0]&&b[0]&&f1.vis1[0][j])
- ||(f0.vis1[i][1]&&b[1]&&f1.vis1[1][j]);
- // 要么走第一行 要么走第二行
- res.vis2[0]=f0.vis2[0]
- ||(f0.vis1[0][0]&&b[0]&&f1.vis2[0]&&b[1]&&f0.vis1[1][1]);
- // 要么在左节点范围内成立 要么是整个范围成立
- res.vis2[1]=f1.vis2[1]
- ||(f1.vis1[0][0]&&b[0]&&f0.vis2[1]&&b[1]&&f1.vis1[1][1]);
- // 要么在左节点范围内成立 要么是整个范围成立
- return res;
- }
- // 合并最关键
- line_tree find(int rt,int L,int R)
- {
- if(L<=l[rt]&&r[rt]<=R) return f[rt];
- if(R<=m[rt]) return find(lc,L,R);
- if(L>m[rt]) return find(rc,L,R);
- return merge(find(lc,L,R),find(rc,L,R),b[rt]);
- // 最后一处是将两个区间合并起来
- }
- void change(int rt,int x1,int y1,int x2,int y2,int val)
- {
- if(x1==x2&&y1==m[rt])
- // 刚好是 y1==mid y2==mid+1 并且在同一行的情况
- {
- b[rt][x1]=val;
- f[rt]=merge(f[lc],f[rc],b[rt]); // 更新节点信息
- }
- else if(l[rt]==r[rt]) // 不同行的情况 那一定是同列了
- f[rt].vis1[0][1]=f[rt].vis1[1][0]
- =f[rt].vis2[0]=f[rt].vis2[1]=val;
- else
- {
- change(y2<=m[rt]?lc:rc,x1,y1,x2,y2,val);
- // 绝对不会把 y1 y2 分在两个树里 因为最开始已经判断了
- f[rt]=merge(f[lc],f[rc],b[rt]); // 更新节点信息
- }
- }
- void ask(int x1,int y1,int x2,int y2)
- {
- line_tree L=find(1,1,y1);
- line_tree md=find(1,y1,y2);
- line_tree R=find(1,y2,n);
- int res=0;
- for(int i=0;i<2;i++)
- for(int j=0;j<2;j++)
- if(md.vis1[i][j]&&(x1==i||L.vis2[1])&&(x2==j||R.vis2[0]))
- {
- res=1;break;
- }
- puts(res?"Y":"N");
- }
- void build(int rt,int L,int R)
- {
- l[rt]=L;r[rt]=R;m[rt]=((L+R)>>1);
- if(L>=R)
- {
- f[rt].vis1[0][0]=f[rt].vis1[1][1]=1;return ;
- // 一个点 该行到该行坑定是可以的啊
- }
- build(lc,L,m[rt]);build(rc,m[rt]+1,R);
- }
- } T;
- void solve()
- {
- scanf("%d",&n); int x1,x2,y1,y2; T.build(1,1,n);
- while(scanf("%s",str))
- {
- if(str[0]=='E') break;
- scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1--;x2--;
- if(y1>y2) y1^=y2^=y1^=y2,x1^=x2^=x1^=x2;
- if(str[0]=='O') T.change(1,x1,y1,x2,y2,1);
- else if(str[0]=='C') T.change(1,x1,y1,x2,y2,0);
- else T.ask(x1,y1,x2,y2);
- }
- }
- int main()
- {
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2893928.html