Submission #836946

#	Time	Username	Problem	Language	Result	Execution time	Memory
836946		damwuan	Birthday gift (IZhO18_treearray)	C++14	100 / 100	811 ms	74572 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,m,q,up[maxn][19],in[maxn],out[maxn],a[maxn],Time;
set<pii> L[maxn];
vector<int> adj[maxn];
void dfs(int u,int pre)
{
    in[u]=++Time;
    up[u][0]=pre;
    for1(i,1,18)
    {
        up[u][i]=up[up[u][i-1]][i-1];
    }
    for(int v: adj[u])
    {
        if (v==pre) continue;
        dfs(v,u);
    }
    out[u]=Time;
}
bool chk(int u,int v)
{
    return (in[u]<=in[v] && out[v]<=out[u]);
}
int lca(int u,int v)
{
    if (chk(u,v)) return u;
    if (chk(v,u)) return v;
    for2(i,18,0)
    {
        if (!chk(up[u][i],v)) u=up[u][i];
    }
    return up[u][0];
}
void sol()
{
    cin >> n>>m>>q;
    for1(i,2,n)
    {
        int u,v; cin >> u>> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,1);
    //cerr<< chk(4,5)<<" wtf\n";
    for1(i,1,m)
    {
        cin >> a[i];
        L[a[i]].insert({i,i});
    }
    for1(i,1,m-1)
    {

        L[lca(a[i],a[i+1])].insert({i,i+1});
    }
    for1(i,1,q)
    {
        //cerr<< i<<'\n';
        int type; cin >> type;
        if (type==1)
        {
            int pos,u;cin >> pos>>u;
            L[a[pos]].erase({pos,pos});
            L[u].insert({pos,pos});
            if (pos>1)
            {
                L[lca(a[pos],a[pos-1])].erase({pos-1,pos});
                L[lca(u,a[pos-1])].insert({pos-1,pos});
            }
            if (pos<m)
            {
                L[lca(a[pos],a[pos+1])].erase({pos,pos+1});
                L[lca(u,a[pos+1])].insert({pos,pos+1});
            }
            a[pos]=u;
        }
        else
        {
            int l,r,u;cin >> l>> r>>u;
            auto it=L[u].lower_bound({l,l});
            if (it!=L[u].end() && it->se <=r) cout << it->fi << ' '<<it->se<<'\n';
            else cout << -1 << ' '<<-1<<'\n';
        }
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("GROUPDIV.inp","r",stdin);
//    freopen("GROUPDIV.out","w",stdout);

    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

5 4 1
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
*/

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44