Submission #586111

#	Time	Username	Problem	Language	Result	Execution time	Memory
586111		KiriLL1ca	Birthday gift (IZhO18_treearray)	C++14	0 / 100	3 ms	4948 KiB

treearray

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'

using namespace std;
using namespace __gnu_pbds;


typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;
vector <int> g[N];
int up[N][22], tin[N], tout[N], timer = 0;
inline void dfs (int v, int p) {
        up[v][0] = p; tin[v] = timer++;
        for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
        for (auto u : g[v]) {
                if (u == p) continue;
                dfs(u, v);
        }
        tout[v] = timer++;
}
inline bool upper (int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
inline int lca (int a, int b) {
        if (upper(a, b)) return a;
        if (upper(b, a)) return b;
        for (int i = 19; ~i; --i) if (!upper(up[a][i], b)) a = up[a][i];
        return up[a][0];
}

inline void solve () {
        int n, m, q; cin >> n >> m >> q;
        for (int i = 1; i < n; ++i) {
                int u, v; cin >> u >> v; --u; --v;
                g[u].pb(v); g[v].pb(u);
        }
        dfs(0, 0);

        vector <int> a (m);
        for (auto &i : a) cin >> i, --i;
        vector <set <int>> ps (n), pss (n);
        for (int i = 0; i < m; ++i) {
                ps[a[i]].insert(i);
                if (i) pss[lca(a[i - 1], a[i])].insert(i);
        }

        while (q--) {
                int tp; cin >> tp;
                if (tp == 1) {
                        int pos, v; cin >> pos >> v; --pos, --v;
                        ps[a[pos]].erase(pos);
                        if (pos) pss[lca(a[pos - 1], a[pos])].erase(pos);
                        if (pos + 1 < m) ps[lca(a[pos], a[pos + 1])].erase(pos + 1);

                        a[pos] = v;
                        ps[a[pos]].insert(pos);
                        if (pos) pss[lca(a[pos - 1], a[pos])].insert(pos);
                        if (pos + 1 < m) ps[lca(a[pos], a[pos + 1])].insert(pos + 1);
                }
                else {
                        int l, r, v; cin >> l >> r >> v; --l, --r, --v;
                        auto it = ps[v].lower_bound(l);
                        if (it != ps[v].end() && *it <= r) cout << *it + 1 << " " << *it + 1 << endl;
                        else {
                                auto itt = pss[v].lower_bound(l + 1);
                                if (itt != pss[v].end() && *itt <= r) cout << *itt << " " << *itt + 1 << endl;
                                else cout << -1 << " " << -1 << endl;
                        }
                }
        }
}

/// [a [b c]] 
/// [[a b] c]

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

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