Submission #1172777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172777		AtabayRajabli	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4066 ms	53664 KiB

treearray

#include <bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 1, inf = 1e18;
int n, m, q, cnt, dp[20][sz], in[sz], out[sz], sg[sz << 2], a[sz];
vector<int> g[sz];

void dfs(int v, int p)
{
    dp[0][v] = p;
    in[v] = ++cnt;
    for(int i : g[v])
    {
        if(i == p) continue;
        dp[0][i] = v;
        dfs(i, v);
    }
    out[v] = cnt;
}

bool anc(int x, int y)
{
    return in[x] <= in[y] && out[y] <= out[x];
}

int lca(int u, int v)
{
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    for(int i = 19; i >= 0; i--)
    {
        if(!anc(dp[i][u], v)) u = dp[i][u];
    }
    return dp[0][u];
}

void build(int ind, int l, int r)
{
    if(l == r)
    {
        sg[ind] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ind << 1, l, mid);
    build(ind << 1 | 1, mid + 1, r);
    sg[ind] = lca(sg[ind << 1], sg[ind << 1 | 1]);
}

int get(int ind, int l, int r, int lx, int rx)
{
    if(l > rx || r < lx) return -1;
    if(lx <= l && r <= rx) 
    {
        return sg[ind];
    }
    int mid = (l + r) >> 1;
    int left = get(ind << 1, l, mid, lx, rx);
    int right = get(ind << 1 | 1, mid + 1, r, lx, rx);
    if(left > 0 && right > 0) return lca(left, right);
    if(left > 0) return left;
    return right;
}

void upd(int ind, int l, int r, int x, int v)
{
    if(l == r)
    {
        sg[ind] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) upd(ind << 1, l, mid, x, v);
    else upd(ind << 1 | 1, mid + 1, r, x, v);
    sg[ind] = lca(sg[ind << 1], sg[ind << 1 | 1]);
}

void solve()
{
    out[0] = inf;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i < 20; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    build(1, 1, m);
    while(q--)
    {
        int t;
        cin >> t;
        if(t == 1)
        {
            int pos, v;
            cin >> pos >> v;
            upd(1, 1, m, pos, v);
        }
        else
        {
            int l, r, v, x = -1, y = -1;
            cin >> l >> r >> v;
            for(int i = l; i <= r; i++)
            {
                int lb = i, rb = r;
                while(lb <= rb)
                {
                    int mid = (lb + rb) >> 1;
                    int res = get(1, 1, m, i, mid);
                    if(anc(v, res)) lb = mid + 1;
                    else rb = mid - 1;
                }
                int ind = lb - 1;
                if(i <= ind && ind <= r && get(1, 1, m, i, ind) == v) 
                {
                    x = i, y = ind;
                    break;
                }
            }
            cout << x << ' ' << y << '\n';
        }
    }
}

signed main()
{                                                                  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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