제출 #651206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651206		becaido	Birthday gift (IZhO18_treearray)	C++17	56 / 100	387 ms	1224 KiB

treearray

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 4005;
const int H = __lg (SIZE) + 2;

int n, m, q, cnt;
int h[SIZE], in[SIZE], out[SIZE], dfsp[SIZE];
int L[SIZE][H + 1], R[SIZE][H + 1], lc[4 * SIZE];
vector<int> adj[SIZE];
int a[SIZE];

int chmin (int i, int j) {
    return h[i] < h[j] ? i : j;
}

int lca (int i, int j) {
    int l = in[i], r = in[j];
    if (l > r) swap (l, r);
    int t = __lg (r - l + 1);
    return chmin (L[l][t], R[r][t]);
}

void dfs (int pos, int fa) {
    dfsp[++cnt] = pos;
    in[pos] = out[pos] = cnt;
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        dfs (np, pos);
        dfsp[++cnt] = pos;
        out[pos] = cnt;
    }
}

void Pull (int pos, int l, int r) {
    lc[pos] = lca (lc[lpos], lc[rpos]);
}

void build (int pos, int l, int r) {
    if (l == r) {
        lc[pos] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build (lpos, l, mid);
    build (rpos, mid + 1, r);
    Pull (pos, l, r);
}

void upd (int pos, int l, int r, int p, int x) {
    if (l == r) {
        lc[pos] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd (lpos, l, mid, p, x);
    else upd (rpos, mid + 1, r, p, x);
    Pull (pos, l, r);
}

int que (int pos, int l, int r, int L, int R) {
    if (l > r) return 0;
    if (l == L && r == R) return lc[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return que (lpos, l, r, L, mid);
    else if (l > mid) return que (rpos, l, r, mid + 1, R);
    return lca (que (lpos, l, mid, L, mid), que (rpos, mid + 1, r, mid + 1, R));
}

pair<int, int> cal (int l, int r, int v) {
    for (int i = l, j = l - 1; i <= r; i++) {
        j = max (j, i - 1);
        while (j < r) {
            j++;
            int p = que (1, i, j, 1, m);
            //cout << "i = " << i << ", j = " << j << ", p = " << p << '\n';
            if (p == v) return {i, j};
            if (h[p] <= h[v]) {j--; break;}
            if (in[p] < in[v] || in[p] > out[v]) {j--; break;}
        }
    }
    return {-1, -1};
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    h[1] = 1;
    dfs (1, 1);
    FOR (i, 1, cnt) L[i][0] = R[i][0] = dfsp[i];
    for (int t = 1; (1 << t) < cnt; t++) {
        int len = 1 << t, half = len >> 1;
        FOR (i, 1, cnt - len + 1) L[i][t] = chmin (L[i][t - 1], L[i + half][t - 1]);
        for (int i = cnt; i >= len; i--) R[i][t] = chmin (R[i][t - 1], R[i - half][t - 1]);
    }
    FOR (i, 1, m) cin >> a[i];
    build (1, 1, m);
    while (q--) {
        int ty, l, r, p, v;
        cin >> ty;
        if (ty == 1) {
            cin >> p >> v;
            upd (1, 1, m, p, v);
            a[p] = v;
        } else {
            cin >> l >> r >> v;
            auto [x, y] = cal (l, r, v);
            cout << x << ' ' << y << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}
/*
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: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44