Submission #628796

#	Time	Username	Problem	Language	Result	Execution time	Memory
628796		BackNoob	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1394 ms	124040 KiB

treearray

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
int n;
int m;
int q;
int a[mxN];
int depth[mxN];
int par[mxN][LOG + 2];
vector<int> adj[mxN];
multiset<int> pos[mxN];
multiset<int> lca[mxN];
 
void dfs(int u, int p)
{
	for(int v : adj[u]) {
		if(v == p) continue;
		par[v][0] = u;
		depth[v] = depth[u] + 1;
		dfs(v, u);
	}
}

int getlca(int u, int v)
{
	if(depth[u] < depth[v]) swap(u, v);

	for(int j = LOG; j >= 0; j--) 
		if(depth[par[u][j]] >= depth[v]) u = par[u][j];

	if(u == v) return u;

	for(int j = LOG; j >= 0; j--) {
		if(par[u][j] != par[v][j]) {
			u = par[u][j];
			v = par[v][j];
		}
	}
	return par[u][0];
}
void solve()
{
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	par[1][0] = 1;
	dfs(1, -1);


	for(int j = 1; j <= LOG; j++)
	for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];


	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		pos[a[i]].insert(i);
	}

	for(int i = 1; i < m; i++) {
		lca[getlca(a[i], a[i + 1])].insert(i);
	}


	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int p, val;
			cin >> p >> val;

			pos[a[p]].erase(pos[a[p]].find(p));
			if(p > 1) {
				int _lca = getlca(a[p], a[p - 1]);
				lca[_lca].erase(lca[_lca].find(p - 1));
			}
			if(p < m) {
				int _lca = getlca(a[p], a[p + 1]);
				lca[_lca].erase(lca[_lca].find(p));
			}
			a[p] = val;
			pos[a[p]].insert(p);

			if(p < m) {
				int _lca = getlca(a[p], a[p + 1]);
				lca[_lca].insert(p);
			}
			if(p > 1) {
				int _lca = getlca(a[p], a[p - 1]);
				lca[_lca].insert(p - 1);
			}
		}
		else {
			int l, r, x;
			cin >> l >> r >> x;

			auto it = pos[x].lower_bound(l);
			if(it != pos[x].end()) {
				int tmp = *it;
				if(tmp <= r) {
					cout << tmp << ' ' << tmp << endl;
					continue;
				}
			}

			it = lca[x].lower_bound(l);
			if(it != lca[x].end()) {
				int tmp = *it;
				if(tmp + 1 <= r) {
					cout << tmp << ' ' << tmp + 1 << endl;
					continue;
				}
			}
			cout << -1 << ' ' << -1 << endl;

		}
	}


}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

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