제출 #585779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585779		Zanite	Birthday gift (IZhO18_treearray)	C++17	0 / 100	7 ms	10012 KiB

treearray

// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;

#define fi first
#define se second

const int maxN	= 2e5 + 5;
const int logN	= 19;

int n, m, q, a[maxN];

vector<int> adj[maxN];
int tin[maxN], tout[maxN], depth[maxN];
vector<int> Euler;

struct SparseTable {
	int s;
	vector<vector<pii>> ST;

	void build() {
		s = Euler.size();

		ST.push_back(vector<pii>(0));
		for (auto i : Euler) {
			ST[0].push_back({depth[i], i});
		}

		for (int i = 1; i < logN; i++) {
			ST.push_back(vector<pii>(s));

			for (int j = 0; j <= s - (1 << i); j++) {
				ST[i][j] = min(ST[i-1][j], ST[i-1][j + (1 << (i-1))]);
			}
		}
	}

	pii query(int l, int r) {
		int d = r - l + 1;
		int t = 31 - __builtin_clz(d);

		return min(ST[t][l], ST[t][r - (1 << t) + 1]);
	}

	void print() {
		for (auto i : ST) {
			for (auto j : i) {
				printf("{%d, %d} ", j.fi, j.se);
			}
			printf("\n");
		}
	}
} TreeData;

void dfs(int cur, int par, int dpt) {
	Euler.push_back(cur);
	tin[cur] = Euler.size()-1;
	depth[cur] = dpt;

	for (auto nxt : adj[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, dpt+1);
		Euler.push_back(cur);
	}

	tout[cur] = Euler.size()-1;
}

int LCA(int x, int y) {
	//cerr << "LCA " << x << " " << y << '\n';
	if (x == 0) return y;
	if (y == 0) return x;
	if (x > y) swap(x, y);
	return TreeData.query(tin[x], tin[y]).se;
}

bool isAncestor(int x, int y) {
	// is x an ancestor of y?
	return (LCA(x, y) == x);
}

struct Segtree {
	int sz;
	vector<int> seg;

	Segtree(int sz) : sz(sz) {
		seg.assign((sz << 2) + 1, 0);
	}

	void build(int pos, int l, int r) {
		if (l == r) {
			seg[pos] = a[l];
			return;
		}

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		build(lc, l, m);
		build(rc, m+1, r);
		seg[pos] = LCA(seg[lc], seg[rc]);
	}
	void build() {build(1, 1, sz);}

	void update(int pos, int l, int r, int idx, int val) {
		if (l == r) {
			seg[pos] = val;
			return;
		}

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		if (idx <= m) {
			update(lc, l, m, idx, val);
		} else {
			update(rc, m+1, r, idx, val);
		}
		seg[pos] = LCA(seg[lc], seg[rc]);
	}
	void update(int idx, int val) {update(1, 1, sz, idx, val);}

	int query(int pos, int l, int r, int ql, int qr) {
		if (l > qr || ql > r) return 0;
		if (ql <= l && r <= qr) return seg[pos];

		int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		return LCA(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
	}
	int query(int ql, int qr) {return query(1, 1, sz, ql, qr);}

} S(1);

#define debug(x) //cerr << #x << " = " << (x) << '\n'

pii solve(int l, int r, int v) {
	for (int i = l; i <= r; i++) {
		debug(i); debug(a[i]);
		
		if (!isAncestor(a[i], v) && !isAncestor(v, a[i])) continue;

		int cl = i, cr = r;
		while (cl <= cr) {
			debug(cl); debug(cr);
			int cm = (cl + cr) >> 1;
			int x = S.query(i, cm);
			
			if (x == v) {
				return {i, cm};
			} else if (isAncestor(x, v)) {
				cr = cm - 1;
			} else {
				cl = cm + 1;
			}
		}
	}

	return {-1, -1};
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int u, v, i = 1; i < n; i++) {
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 0);
	TreeData.build();

	/*
	TreeData.print();
	for (int i = 1; i <= n; i++) {
		cout << tin[i] << '\n';
	}
	*/

	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}
	S = Segtree(m);
	S.build();

	for (int typ, pos, l, r, v, i = 1; i <= q; i++) {
		scanf("%d", &typ);

		if (typ == 1) {
			scanf("%d %d", &pos, &v);
			a[pos] = v;
			S.update(pos, v);

		} else {
			scanf("%d %d %d", &l, &r, &v);
			pii ans = solve(l, r, v);
			printf("%d %d\n", ans.fi, ans.se);

		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'int main()':
treearray.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
treearray.cpp:187:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |    scanf("%d %d", &pos, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |    scanf("%d %d %d", &l, &r, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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