自动搬运

查看原文

来自洛谷，原作者为

	WuMin4 已摆烂求放过

搬运于2025-08-24 23:14:55，当前版本为作者最后更新于2025-04-25 09:19:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[eJOI 2024] 古迹漫步 / Old Orhei

思路

可以发现 $T$ 的范围特别大，每次操作对 $T$ 进行单点修改区间查询，考虑用线段树维护信息并转移。

发现 $N\le 50$，于是考虑暴力维护初始在每个点时经过了一段区间的操作后到达了哪个点。该信息上传是简单的。若操作了 $T_l\sim T_{mid}$ 后 $x$ 可以到达 $y$，操作 $T_{mid}\sim T_r$ 后 $y$ 可以到达 $z$，则操作 $T_l\sim T_r$ 后 $x$ 可以到达 $z$。

时间复杂度为 $O(NQ\log T)$，可以通过。

代码

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs ((u<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
struct node{
	int x,y;
}b[100005];
int n,m,T,Q,to[400005][55],a[100005];
void push_up(int u){
	for(int i=1;i<=n;i++)
		to[u][i]=to[rs][to[ls][i]];
}
void build(int u,int l,int r){
	if(l==r){
		for(int i=1;i<=n;i++) to[u][i]=i;
		to[u][b[a[l]].x]=b[a[l]].y;
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void upd(int u,int l,int r,int x,int v){
	if(l==r){
		for(int i=1;i<=n;i++) to[u][i]=i;
		to[u][b[v].x]=b[v].y;
		return;
	}
	if(x<=mid) upd(ls,l,mid,x,v);
	else upd(rs,mid+1,r,x,v);
	push_up(u);
}
int qu(int u,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y) return to[u][v];
	int res=v;
	if(x<=mid) res=qu(ls,l,mid,x,y,res);
	if(mid<y) res=qu(rs,mid+1,r,x,y,res);
	return res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>b[i].x>>b[i].y;
	cin>>T;
	for(int i=1;i<=T;i++)
		cin>>a[i];
	build(1,1,T);
	cin>>Q;
	while(Q--){
		int op,l,r,x;
		cin>>op;
		if(op==1)
			cin>>l>>r>>x,cout<<qu(1,1,T,l,r,x)<<endl;
		else
			cin>>l>>x,upd(1,1,T,l,x);
	}
	return 0; 
}