Submission #319309

#	Time	Username	Problem	Language	Result	Execution time	Memory
319309		BeanZ	Birthday gift (IZhO18_treearray)	C++14	56 / 100	795 ms	262148 KiB

treearray

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
//#define task "A"
#define ll int
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int lg = 18;
ll dp[N][lg + 1], dep[N];
vector<ll> node[N];
struct LCA{
    ll lca(ll u, ll v){
        if (dep[v] < dep[u]) swap(u, v);
        ll dis = dep[v] - dep[u];
        for (int i = lg; i >= 0; i--){
            if (dis & (1 << i)){
                v = dp[v][i];
            }
        }
        if (v == u) return u;
        for (int i = lg; i >= 0; i--){
            if (dp[u][i] != dp[v][i]){
                v = dp[v][i];
                u = dp[u][i];
            }
        }
        return dp[u][0];
    }
    void dfs(ll u, ll v){
        for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for (auto j : node[u]){
            if (j == v) continue;
            dep[j] = dep[u] + 1;
            dp[j][0] = u;
            dfs(j, u);
        }
    }
} tree;
struct ST{
    multiset<ll> s[N * 4];
    void add(ll k, ll l, ll r, ll x, ll v){
        if (x > r || x < l) return;
        s[k].insert(v);
        if (l == r){
            return;
        }
        ll mid = (l + r) >> 1;
        add(k << 1, l, mid, x, v);
        add(k << 1 | 1, mid + 1, r, x, v);
    }
    void del(ll k, ll l, ll r, ll x, ll v){
        if (x > r || x < l) return;
        s[k].erase(s[k].find(v));
        if (l == r) return;
        ll mid = (l + r) >> 1;
        del(k << 1, l, mid, x, v);
        del(k << 1 | 1, mid + 1, r, x, v);
    }
    ll get(ll k, ll l, ll r, ll x, ll y, ll v){
        if (x > r || y < l) return 0;
        if (s[k].find(v) == s[k].end()) return 0;
        ll mid = (l + r) >> 1;
        if (x <= l && y >= r){
            if (l == r) return l;
            if (s[k << 1].find(v) != s[k << 1].end()) return get(k << 1, l, mid, x, y, v);
            else return get(k << 1 | 1, mid + 1, r, x, y, v);
        }
        return max(get(k << 1, l, mid, x, y, v), get(k << 1 | 1, mid + 1, r, x, y, v));
    }
} st1, st2;
ll a[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    ll n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++){
        ll u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    tree.dfs(1, 1);
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i < m; i++) st1.add(1, 1, m - 1, i, tree.lca(a[i], a[i + 1]));
    for (int i = 1; i <= m; i++) st2.add(1, 1, m, i, a[i]);
    while (q--){
        ll task;
        cin >> task;
        if (task == 1){
            ll x, v;
            cin >> x >> v;
            st2.del(1, 1, m, x, a[x]);
            st2.add(1, 1, m, x, v);
            if (x < m) st1.del(1, 1, m - 1, x, tree.lca(a[x], a[x + 1]));
            if (x < m) st1.add(1, 1, m - 1, x, tree.lca(v, a[x + 1]));
            if (x > 1) st1.del(1, 1, m - 1, x - 1, tree.lca(a[x - 1], a[x]));
            if (x > 1) st1.add(1, 1, m - 1, x - 1, tree.lca(a[x - 1], v));
            a[x] = v;
        } else {
            ll l, r, v;
            cin >> l >> r >> v;
            ll ans = st1.get(1, 1, m - 1, l, r - 1, v);
            if (ans == 0){
                ll tmp = st2.get(1, 1, m, l, r, v);
                if (tmp != 0) cout << tmp << " " << tmp << endl;
                else cout << -1 << " " << -1 << endl;
            }
            else cout << ans << " " << ans + 1 << endl;
        }
    }
}
/*
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
*/

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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