自动搬运

查看原文

来自洛谷，原作者为

	AThousandSuns Simultaneous release!

搬运于2025-08-24 21:58:08，当前版本为作者最后更新于2019-01-16 17:33:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

线段树神题……没想到线段树还有这种玩法……

打出这道题对线段树的理解和运用一定有巨大帮助。

---

这题一看像是LCT的样子，然而LCT还得支持各种奇怪的东西，还有巨大常数……一不小心就会挂。

考虑线段树。咋啥都能考虑

一个节点维护 $[l,r]$ 区间的联通情况。（不考虑 $[l,r]$ 外的道路，不然会写死人）

（u,d,l,r,p,q都是bool。下图中有个错别字，懒得改了）

对于叶子节点，很明显：

---

本题最恶心也是最厉害的地方来了：pushup。

先看看l。

r同理。这一部分这样写：

//conn[x][0]表示(1,x)和(1,x+1)是否联通
//conn[x][1]表示(2,x)和(2,x+1)是否联通
x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
//左边能直接走下去
//左边能走上面，中上联通，再通过右边走到下面，中下联通，再通过左边走下面绕回来
x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
//同理

再看看u。

d同理。这一部分这样写：

x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
//左边能走上面，中上联通，右边能走上面
//左边能走主对角线，中下联通，右边能走副对角线
x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
//同理

最后还有p：

q同理。最后放出整个pushup代码：

//pushup这样传参的原因待会会说
void pushup(node &x,node l,node r){
	x.lft=l.lft;	//x的左边界，因为conn要用到所以也要pushup
	x.rig=r.rig;	//x的右边界
	x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
	x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
	x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
	x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
	x.p=(l.u&conn[l.rig][0]&r.p)|(l.p&conn[l.rig][1]&r.d);
	x.q=(l.d&conn[l.rig][1]&r.q)|(l.q&conn[l.rig][0]&r.u);
}

---

现在来写修改操作。

我们发现在同一行和不在同一行有很多区别（要改的东西不一样），那就分开讨论。

先看不在同一行：（即同一列）

对于这一列代表的叶子节点，实际上就是上面和下面的连通性发生了变化。

然后沿途pushup就行了。

在同一行的会比较难懂。我也是看了别的题解才明白……

发现对于 $[x,x+1]$ 这两个点所在的列，直接找到 $x$ 对应的线段树叶子不太好修改。怎么弄呢？

我们发现，修改 $[x,x+1]$ 这两列，会影响到的最小线段树节点是 $[l,r]$，其中 $x=(l+r)/2=mid$。即 $x$ 作为线段树节点中点的节点。

会怎么影响呢？其实就是conn会变，然后就会影响整个节点的联通性。

那么修改完conn之后，对这个节点重新pushup一遍就好了。

这里贴个代码：

//o：节点编号，l：左端点，r：右端点
//p,row：表示修改(row+1,p)和(row+1,p+1)，因为第一行在conn是0，第二行是1
//val：开还是关
void modify1(int o,int l,int r,int p,int row,bool val){
	int mid=(l+r)>>1;
	if(mid==p){	//中点就是p
		conn[mid][row]=val;	//修改conn
		pushup(seg[o],seg[o<<1],seg[o<<1|1]);	//重新pushup
		return;
	}
	if(mid>=p) modify1(lson,p,row,val);	//递归修改
	else modify1(rson,p,row,val);
	pushup(seg[o],seg[o<<1],seg[o<<1|1]);	//更新
}

---

最后还有询问。询问相信大家都会写。

//返回node方便在递归路上合并各个节点的信息
node query(int o,int l,int r,int ql,int qr){
	if(l>=ql && r<=qr) return seg[o];	//直接返回
	int mid=(l+r)>>1;
	if(mid<ql) return query(rson,ql,qr);	//不需要左儿子
	if(mid>=qr) return query(lson,ql,qr);	//不需要有儿子
	node ans;
	pushup(ans,query(lson,ql,qr),query(rson,ql,qr));	//左右儿子合起来
	return ans;
} 

然后main里面大力讨论一下是考虑答案u,d,l,r,p还是q。交上去……

WA？？？？？？！！！！！！

哦对了，我们来测组数据吧：

4
OPEN 1 1 1 2
OPEN 1 3 1 4
OPEN 1 1 2 1
OPEN 2 1 2 2
OPEN 2 2 2 3
OPEN 2 3 2 4
OPEN 1 4 2 4
ASK 1 2 1 3 
EXIT

答案明显是Y。但是我们输出了N？为什么？

我们把这个图画出来：

原来如此。那么求出三个区间大力讨论一下。写法跟pushup差不多，如果理解了pushup那么这一块也应该不难理解。

直接放代码吧：

#include<bits/stdc++.h>
using namespace std;
const int maxn=444444;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	char ch=getchar();int x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
struct node{
	int lft,rig;
	bool l,r,u,d,p,q;
}seg[maxn];	//节点
int n;
bool conn[maxn][2];
void pushup(node &x,node l,node r){
	x.lft=l.lft;
	x.rig=r.rig;
	x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
	x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
	x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
	x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
	x.p=(l.u&conn[l.rig][0]&r.p)|(l.p&conn[l.rig][1]&r.d);
	x.q=(l.d&conn[l.rig][1]&r.q)|(l.q&conn[l.rig][0]&r.u);
}
void build(int o,int l,int r){	//建树
	if(l==r){
		seg[o].lft=seg[o].rig=l;	//叶子节点左右边界
		seg[o].u=seg[o].d=1;	//左右联通
		return;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
void modify1(int o,int l,int r,int p,int row,bool val){	//同行修改
	int mid=(l+r)>>1;
	if(mid==p){
		conn[mid][row]=val;
		pushup(seg[o],seg[o<<1],seg[o<<1|1]);
		return;
	}
	if(mid>=p) modify1(lson,p,row,val);
	else modify1(rson,p,row,val);
	pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
void modify2(int o,int l,int r,int p,bool val){	//不同行修改，第p列
	if(l==r){
		seg[o].l=seg[o].r=seg[o].p=seg[o].q=val;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=p) modify2(lson,p,val);
	else modify2(rson,p,val);
	pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
node query(int o,int l,int r,int ql,int qr){	//查询区间[ql,qr]的节点
	if(l>=ql && r<=qr) return seg[o];
	int mid=(l+r)>>1;
	if(mid<ql) return query(rson,ql,qr);
	if(mid>=qr) return query(lson,ql,qr);
	node ans;
	pushup(ans,query(lson,ql,qr),query(rson,ql,qr));
	return ans;
} 
int main(){
	n=read();char op[10];
	build(1,1,n);
	while(~scanf("%s",op) && op[0]!='E'){
		int a=read(),b=read(),c=read(),d=read();
		switch(op[0]){
			case 'C':	//关路
				if(a==c) modify1(1,1,n,min(b,d),a-1,0);	//同一行
				else modify2(1,1,n,b,0);	//不同行
				break;
			case 'O':	//开路
				if(a==c) modify1(1,1,n,min(b,d),a-1,1);
				else modify2(1,1,n,b,1);
				break;
			case 'A':	//询问
				if(b>d) swap(a,c),swap(b,d);	//列编号小的放前面
				node ans1=query(1,1,n,b,d),ans2=query(1,1,n,1,b),ans3=query(1,1,n,d,n);	//三段
				bool flag=false;
				if(a==1){
					if(c==1){	//左上，右上
						if(ans1.u) flag=true;	//直接走上面
						if(ans2.r&ans1.d&ans3.l) flag=true;	//绕路走
					}
					else{	//左上，右下
						if(ans1.p) flag=true;	//直接走
						if(ans2.r&ans1.d) flag=true;	//从左边绕
						if(ans3.l&ans1.u) flag=true;	//从右边绕
					}
				}
				else{
					if(c==1){	//左下，右上
						if(ans1.q) flag=true;	//直接走
						if(ans2.r&ans1.u) flag=true;	//从左边绕
						if(ans3.l&ans1.d) flag=true;	//从右边绕
					}
					else{	//左下，右下
						if(ans1.d) flag=true;	//直接走
						if(ans2.r&ans1.u&ans3.l) flag=true;	//绕路走
					}
				}
				puts(flag?"Y":"N");
		}
	}
}

---

这可能是我写过最认真的一篇题解了。

主要还是因为这题太有意义了，而且洛谷上题解没几个图，有点难懂……

希望能帮到大家。两开花，谢谢支持。