正能量软件不良网站直播,重庆市建设工程造价管理总网站,咖啡网页制作素材,企业制作网站公司题目链接 分析#xff1a; 这道题的题解很长#xff0c;所以就不粘题面了#xff0c;我们一点一点讲明白这道题 很荣幸#xff0c;我看了题面之后 想到了这道题 可以很高兴的发现10w是线段树能够承受的范围 我们可以利用线段树维护连通性#xff0c;每个节点内我们要维… 题目链接 分析 这道题的题解很长所以就不粘题面了我们一点一点讲明白这道题 很荣幸我看了题面之后 想到了这道题 可以很高兴的发现10w是线段树能够承受的范围 我们可以利用线段树维护连通性每个节点内我们要维护6个信息分别表示连通性 读入完成后我们面临的第一个问题就是道路的状态改变 这就牵扯到了一个change函数 在link函数中 我们只维护了向下走的直接连通性 至于其他的连通性我们在update函数中完成 ask函数 这次默认列数小的点为第一个点 这两个点就把整个序列分成了3个部分 1~c1,c1~c2,c2~n 我们通过get函数求出这三个部分的连通情况 之后就是特判了 tip 题目中的(r1,c1) 表示的是第r1行第c1列 第一次交上去WA 之后就是一句一句的排查 终于把问题锁定在了ask函数中 一开始以为是特判的问题但是查了半天也没有什么异常 最后才发现是在get的时候 手残把c1,c2写错了 这里写代码片
#includecstdio
#includecstring
#includeiostreamusing namespace std;const int N100010;
struct node{bool x[2],y[2],z[2];
};
node t[N2];
int n,r1,r2,c1,c2;
bool a[N][2][2];
char opt[10];
int dx[3]{-1,0,1}; //每个点只能与三个点直接相连
int dy[3]{0,1,0};void build(int bh,int l,int r)
{if (lr){t[bh].x[0]1; //横向 t[bh].x[1]1;return;} int mid(lr)1;build(bh1,l,mid);build(bh1|1,mid1,r);
}void update(node bh,node lc,node rc,int mid)
{bh.x[0](lc.x[0]a[mid][0][0]rc.x[0])||(lc.z[0]a[mid][1][0]rc.z[1]); //左上-右上 bh.x[1](lc.x[1]a[mid][1][0]rc.x[1])||(lc.z[1]a[mid][0][0]rc.z[0]); //左下-右下 bh.y[0]lc.y[0]||(lc.x[0]a[mid][0][0]rc.y[0]a[mid][1][0]lc.x[1]); //左上-左下bh.y[1]rc.y[1]||(rc.x[0]a[mid][0][0]lc.y[1]a[mid][1][0]rc.x[1]); //右上-右下bh.z[0](lc.x[0]a[mid][0][0]rc.z[0])||(lc.z[0]a[mid][1][0]rc.x[1]); //左上-右下 bh.z[1](lc.x[1]a[mid][1][0]rc.z[1])||(lc.z[1]a[mid][0][0]rc.x[0]); //左下-右上
}void link(int bh,int l,int r,int p)
{if (lr) //单点修改 {t[bh].y[0]t[bh].y[1]t[bh].z[0]t[bh].z[1]a[p][0][1];t[bh].x[0]t[bh].x[1]1;return;} int mid(lr)1;if (pmid) link(bh1,l,mid,p);else link(bh1|1,mid1,r,p);update(t[bh],t[bh1],t[bh1|1],mid);
}void change(bool o)
{int d;for (int i0;i3;i)if (c1dx[i]c2r1dy[i]r2) //两个点的相对位置di;if (d0) a[c2][r2][0]o,link(1,1,n,c2); //1--2 左 else if (d1) a[c1][0][1]o,link(1,1,n,c1); //下 else a[c1][r1][0]o,link(1,1,n,c1); //右
}void get(node p,int bh,int L,int R,int l,int r)
{if (LlRr) {pt[bh];return;}int mid(LR)1;if (rmid) get(p,bh1,L,mid,l,r);else if (lmid) get(p,bh1|1,mid1,R,l,r);else{node t1,t2;get(t1,bh1,L,mid,l,r);get(t2,bh1|1,mid1,R,l,r);update(p,t1,t2,mid);}
}void ask()
{if(c1c2) swap(r1,r2),swap(c1,c2);node p1,p2,p3;get(p1,1,1,n,1,c1);get(p2,1,1,n,c1,c2);get(p3,1,1,n,c2,n);if (r1r2){if (r10){if (p2.x[0]||(p1.y[1]p2.x[1]p3.y[0])||(p1.y[1]p2.z[1])||(p3.y[0]p2.z[0])) printf(Y\n);else printf(N\n);}else{if (p2.x[1]||(p2.x[0]p1.y[1]p3.y[0])||(p1.y[1]p2.z[0])||(p3.y[0]p2.z[1])) printf(Y\n);else printf(N\n);}}else{if (r10){if (p2.z[0]||(p1.y[1]p2.x[1])||(p2.x[0]p3.y[0])) printf(Y\n);else printf(N\n);}else{if (p2.z[1]||(p1.y[1]p2.x[0])||(p3.y[0]p2.x[1])) printf(Y\n);else printf(N\n);}}
}int main()
{scanf(%d,n);build(1,1,n);scanf(%s,opt);while (opt[0]!E){int a,b,c,d;scanf(%d%d%d%d,r1,c1,r2,c2);r1--;r2--;if (r1r2) swap(c1,c2),swap(r1,r2); //点从上到下编号 if (opt[0]O) change(1);else if (opt[0]C) change(0);else ask();scanf(%s,opt);}return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673190.html
