Submission #1301035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301035		paulxaxa	Birthday gift (IZhO18_treearray)	C++20	56 / 100	680 ms	69552 KiB

treearray

#include <bits/stdc++.h>

#define NMAX 200005
#define LOG 18
#define ll long long int
#define MOD 1000000007
#define BASE 128
#define INF (ll)1e17

using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

int n,m,q;
int a[NMAX+1];

set<int> pos[NMAX+1],pos1[NMAX+1];
int timer=0;
int tour[NMAX+1],Start[NMAX+1];
int d[NMAX+1];

int rmq[NMAX+1][LOG+1];
vector<int> adj[NMAX+1];
int p2[NMAX+1];
void dfs(int x,int p)
{
    d[x] = d[p] + 1;
    tour[++timer] = x;
    Start[x] = timer;
    for(int y : adj[x])
    {
        if(y!=p)
        {
            dfs(y,x);
            tour[++timer] = x;
        }
    }
}
int Lca(int x,int y)
{
    x = Start[x];
    y = Start[y];
    if(x > y)
    {
        swap(x,y);
    }
    int k = p2[y-x+1];
    int l = rmq[x][k];
    int r = rmq[y-(1<<k)+1][k];
    return d[l] < d[r] ? l : r;
}
int main()
{

    cin >> n >> m >> q;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=m;i++)
    {
        cin >> a[i];
    }
    dfs(1,0);

    for(int i=1;i<=timer;i++)
    {
        rmq[i][0] = tour[i];
    }

    for(int j=1;j<=LOG;j++)
    {
        for(int i=1;i<=timer;i++)
        {
            rmq[i][j] = rmq[i][j-1];
            if(i + (1<<(j-1)) <= timer)
            {
                int t = rmq[i+(1<<(j-1))][j-1];
                rmq[i][j] = d[t] < d[rmq[i][j]] ? t : rmq[i][j];
            }
        }
    }
    p2[1] = 0;
    for(int i=2;i<=timer;i++)
    {
        p2[i] = p2[i/2] + 1;
    }

    for(int i=2;i<=m;i++)
    {
        pos[Lca(a[i],a[i-1])].insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        pos1[a[i]].insert(i);
    }
    for(int i=1;i<=q;i++)
    {
        int t;
        cin >> t;
        if(t==1)
        {
            int p,v;
            cin >> p >> v;
            if(p > 1)
            {
                pos[Lca(a[p-1],a[p])].erase(p);
                pos[Lca(a[p-1],v)].insert(p);
            }
            if(p < m)
            {
                pos[Lca(a[p],a[p+1])].erase(p+1);
                pos[Lca(v,a[p+1])].insert(p+1);
            }
            pos1[a[p]].erase(p);
            pos1[v].insert(p);
            a[p] = v;
        }
        else
        {
            int l,r,v;
            cin >> l >> r >> v;
            if(l==r)
            {
                if(a[l] == v)
                {
                    cout << l << " " << l << '\n';
                }
                else
                {
                    cout << -1 << " " << -1 << '\n';
                }
            }
            else
            {
                auto it = pos[v].upper_bound(l);
                if(it!=pos[v].end() && *it <= r)
                {
                    int p = *it;
                    cout << p-1 << " " << p << '\n';
                }
                else
                {
                    it = pos1[v].lower_bound(l);
                    if(it!=pos1[v].end() && *it <= r)
                    {
                        cout << *it << " " << *it << '\n';
                    }
                    else
                    {
                        cout << -1 << " " << -1 << '\n';
                    }
                }
            }
        }
    }
}
//5 4 4
//1 2
//3 1
//3 4
//5 3
//4 5 2 3

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