这两天好累啊，写完睡觉。。

Solution

一眼线段树。

但是不太好维护。

看着题目，$L$ 到 $R$ 这个区间求取起点为 $S$ 最终停哪，启发我们让线段树设计为 $tree_{i,j}$ 表示第 $i$ 个节点所管辖区间从 $j$ 出发的终点。

那么只要 push_up 写得出来，那就结束了。

思考一下，发现很简单。具体柿子如下

其中 $lc(x)$ 表示 $x$ 的左孩子，$rc$ 同理。

然后就结束了。

关于查询函数的实现，貌似有一点小细节，但是道理跟 push_up 一样，可以尝试自己写或者参考我的代码。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
const int N=1e5+5;
int n,m,t,q,a[N],opt,l,r,s,x,tree[4*N][55];
pair<int,int> b[N];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
inline void push_up(int now){
	for(int i = 1;i<=n;i++)
		tree[now][i]=tree[rc(now)][tree[lc(now)][i]];
}
inline void build(int now,int l,int r){
	if(l==r){
		for(int i = 1;i<=n;i++)
			if(i==b[a[l]].first)
				tree[now][i]=b[a[l]].second;
			else
				tree[now][i]=i;
		return;
	}
	build(lc(now),l,mid);
	build(rc(now),mid+1,r);
	push_up(now);
}
inline void update(int now,int l,int r,int x,int y){
	if(l>x||r<x) return;
	if(l==r){
		a[x]=y;
		for(int i = 1;i<=n;i++)
			if(i==b[a[l]].first)
				tree[now][i]=b[a[l]].second;
			else
				tree[now][i]=i;
		return;
	}
	update(lc(now),l,mid,x,y);
	update(rc(now),mid+1,r,x,y);
	push_up(now);
}
inline int query(int now,int l,int r,int ql,int qr,int s){
	if(l>=ql&&r<=qr) return tree[now][s];
	if(mid<ql) return query(rc(now),mid+1,r,ql,qr,s);
	if(mid+1>qr) return query(lc(now),l,mid,ql,qr,s);
	int ss=query(lc(now),l,mid,ql,qr,s);
	return query(rc(now),mid+1,r,ql,qr,ss);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
		cin>>b[i].first>>b[i].second;
	cin>>t;
	for(int i = 1;i<=t;i++) cin>>a[i];
	build(1,1,t);
	cin>>q;
	while(q--){
		cin>>opt;
		if(opt==1) cin>>l>>r>>s,cout<<query(1,1,t,l,r,s)<<'\n';
		else cin>>x>>s,update(1,1,t,x,s);
	}
	return 0;
}