题解：P12335 [eJOI 2024] 古迹漫步 / Old Orhei

WuMin4 · 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; 
}