Submission #1301038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301038		paulxaxa	Birthday gift (IZhO18_treearray)	C++17	100 / 100	827 ms	121120 KiB

treearray

    #include <bits/stdc++.h>

    #define NMAX 400005
    #define LOG 20
    #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: 44 / 44