Submission #1132012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132012		lopkus	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	6724 KiB

treearray

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

vector<int> a(N);

struct Lca{
    vector<int>adj[N];
    int in[N];
    int out[N];
    int timer=1;
    int P[N];
    int Log(int n){
        int logs[n+1];
        logs[1]=0;
        for(int i=2;i<=n;i++)logs[i]=logs[i/2]+1;
        return logs[n];
    }
    int up[N][30];
    void build(int n){
        up[1][0]=1;
        for(int i=2;i<=n;i++)up[i][0]=P[i];
        for(int i=1;i<=29;i++){
            for(int j=1;j<=n;j++){
                up[j][i]=up[up[j][i-1]][i-1];
            }
        }
    }
    void add(int u,int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs(int x,int cale){
        in[x]=timer++;
        P[x]=cale;
        for(auto it:adj[x]){
            if(it!=cale)dfs(it,x);
        }
        out[x]=timer;
    }
    int in_tree(int u,int v){
        return in[u]<=in[v]&&out[u]>=out[v];
    }
    int lca(int u,int v){
        if(u==v)return u;
        if(in_tree(u,v))return u;
        if(in_tree(v,u))return v;
        for(int i=29;i>=0;i--){
            if(!in_tree(up[u][i],v)){
                u=up[u][i];
            }
        }
        return up[u][0];
    }
}lca;

struct segtree1{
    int t[4*N];
    int query(int v,int tl,int tr,int l,int r){
        if(tl>r||tr<l)return 1e18;
        if(tl>=l&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return min(query(v*2,tl,tm,l,r),query(v*2+1,tm+1,tr,l,r));
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr) {
            t[v] = value;
        }
        else {
            int tm=(tl+tr)/2;
            if(index<=tm)update(v*2,tl,tm,index,value);
            else update(v*2+1,tm+1,tr,index,value);
            t[v]=min(t[v*2],t[v*2+1]);
        }
    }
}seg1;

struct segtree2{
    int t[4*N];
    int query(int v,int tl,int tr,int l,int r){
        if(tl>r||tr<l)return 1e18;
        if(tl>=l&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return min(query(v*2,tl,tm,l,r),query(v*2+1,tm+1,tr,l,r));
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr) {
            t[v] = value;
        }
        else {
            int tm=(tl+tr)/2;
            if(index<=tm)update(v*2,tl,tm,index,value);
            else update(v*2+1,tm+1,tr,index,value);
            t[v]=min(t[v*2],t[v*2+1]);
        }
    }
}seg2;



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        lca.add(u,v);
    }
    lca.dfs(1, 0);
    lca.build(n);
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        seg1.update(1, 1, n, i, a[i]);
    }
    for(int i = 1; i < m; i++) {
        seg2.update(1, 1, n, i, lca.lca(a[i], a[i + 1]));
    }
    while(q--) {
        int type;
        cin >> type;
        if(type == 1) {
            int pos, v;
            cin >> pos >> v;
            a[pos] = v;
            seg1.update(1, 1, n, pos, a[pos]);
            if(pos != n) {
                seg2.update(1, 1, n, pos, lca.lca(a[pos], a[pos + 1]));
            }
            else {
                seg2.update(1, 1, n, pos, lca.lca(a[pos - 1], a[pos]));
            }
        }
        else {
            int l, r, x;
            cin >> l >> r >> x;
            int l1 = - 1, r1 = - 1;
            int L = l, R = r, p = - 1;
            while(L <= R) {
                int mid = (L + R) / 2;
                int u = seg1.query(1, 1, n, l, mid);
                if(u <= x) {
                    R = mid - 1;
                    p = mid;
                }
                else {
                    L = mid + 1;
                }
            }
            if(p != - 1 && a[p] == x) {
                l1 = p;
                r1 = p;
            }
            L = l, R = r - 1, p = - 1;
            while(L <= R) {
                int mid = (L + R) / 2;
                int u = seg2.query(1, 1, n, l, mid);
                if(u <= x) {
                    R = mid - 1;
                    p = mid;
                }
                else {
                    L = mid + 1;
                }
            }
            if(p != - 1 && lca.lca(a[p], a[p + 1]) == x) {
                l1 = p;
                r1 = p + 1;
            }
            cout << l1 << " " << r1 << "\n";
         }
    }
}
/*
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
*/

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