2022.07.26. (Euler Tour Technique) 풀이

다뤄본 태그

• Euler Tour Technique (ABCDE)

A. [2820] 자동차 공장 (Platinum III)

Subtree Add Update와 Point Query입니다.

Euler Tour Technique를 사용하면 우리가 잘 풀 수 있는 형태인 Range Add Update와 Point Query로 바꿀 수 있습니다.

 

아래 쓰인 코드는 Difference 배열을 사용해서

Range Update / Point Query를 Point Update / Range Query로 바꾼 방식입니다.

 

이에 관해 간단히 설명해보자면

\( D_{i} = A_{i} - A_{i-1} \)을 정의한다면, \( A_{i} = \sum_{j=1}^{i} D_{i} \)가 됩니다.

그럼, \( D \)를 기준으로 세그먼트 트리를 만들면 Range Add Update는 2개의 Point Update인 \( D_{st} += x \), \( D_{ed+1} -= x \)로 처리할 수 있고 (imos법 같은 걸 생각해봅시다.)

그 대신 \( A_{i} \)를 출력하기 위해서는 \( [1, i] \)까지의 Range Sum Query를 적용시켜야 합니다.

const int N = 524288; ll seg[1048580];
void upd(int pos, int val){ pos += N-1;
	seg[pos] += val; pos >>= 1;
	while (pos){
		seg[pos] = seg[pos<<1] + seg[pos<<1|1]; pos >>= 1;
	}
}
void upd(int st, int ed, int val){
	upd(st, val); upd(ed+1, -val);
}
ll qry(int st, int ed){ st += N-1; ed += N-1;
	ll res = 0;
	while (st <= ed){
		if (st & 1){ res += seg[st]; st += 1; }
		if (~ed & 1){ res += seg[ed]; ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}
ll qry(int pos){ return qry(1, pos); }

vector<int> chl[500020];
int ord, ind[500020], oud[500020];
void dfs(int now){
	ord += 1; ind[now] = ord;
	for (int nxt : chl[now]){ dfs(nxt); }
	oud[now] = ord;
}

ll arr[500020], dif[500020];
void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		if (i == 1){ cin >> arr[i]; }
		else{ int par; cin >> arr[i] >> par; chl[par].push_back(i); }
	}
	dfs(1);
	for (int i = 1; i <= n; i++){ dif[ ind[i] ] = arr[i]; }
	for (int i = n; i >= 1; i--){ dif[i] -= dif[i-1]; }
	for (int i = 1; i <= n; i++){ upd(i, dif[i]); }
	while (q--){
		char m; cin >> m;
		if (m == 'p'){
			int pos, val; cin >> pos >> val; upd(ind[pos]+1, oud[pos], val);
		}
		if (m == 'u'){
			int pos; cin >> pos;
			cout << qry(ind[pos]) << endl;
		}
	}
}

B. [14268] 회사 문화 2 (Platinum III)

내리 칭찬의 전파 과정을 잘 생각해보면, 결국 서브트리에 있는 모든 직원들이 동일한 양만큼 칭찬을 받는다는 결론이 나오게 됩니다.

즉, 이 문제는 Subtree Add Update와 Point Query 문제이고,

이 문제는 결국 자동차 공장이랑 다른 척 하고 있는 같은 문제라는 결론이 나옵니다.

const int N = 131072; ll seg[262150];
void upd(int pos, int val){ pos += N-1;
	seg[pos] += val; pos >>= 1;
	while (pos){
		seg[pos] = seg[pos<<1] + seg[pos<<1|1]; pos >>= 1;
	}
}
void upd(int st, int ed, int val){
	upd(st, val); upd(ed+1, -val);
}
ll qry(int st, int ed){ st += N-1; ed += N-1;
	ll res = 0;
	while (st <= ed){
		if (st & 1){ res += seg[st]; st += 1; }
		if (~ed & 1){ res += seg[ed]; ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}
ll qry(int pos){ return qry(1, pos); }

vector<int> chl[500020];
int ord, ind[500020], oud[500020];
void dfs(int now){
	ord += 1; ind[now] = ord;
	for (int nxt : chl[now]){ dfs(nxt); }
	oud[now] = ord;
}

ll arr[500020], dif[500020];
void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		int par; cin >> par; if (i > 1){ chl[par].push_back(i); }
	}
	dfs(1);
	while (q--){
		int typ; cin >> typ;
		if (typ == 1){
			int pos, val; cin >> pos >> val; upd(ind[pos], oud[pos], val);
		}
		if (typ == 2){
			int pos; cin >> pos;
			cout << qry(ind[pos]) << endl;
		}
	}
}

C. [10565] Salary Inequity (Platinum II)

일단 업데이트는 이전 문제와 동일합니다. Subtree Add Update입니다.

하지만, 이번에는 출력하는 게 좀 달라졌습니다.

그렇다고 많이 어려워진 건 아니고, max(subtree) - min(subtree)를 출력하면 됩니다.

이는 min, max를 관리하는 세그먼트 트리를 들고 있으면 됩니다.

vector<int> adj[1000020];
pi2 ord[1000020]; int cnt = 0;
void dfs(int now, int nxt){
	cnt += 1; ord[now].fr = cnt;
	for (int nxt : adj[now]){ dfs(nxt, now); }
	ord[now].sc = cnt;
}

const int INF = 1e9;
const int N = 1048576; pi3 seg[2097160];
void pro(int ni, int ns, int ne){
	if (ns != ne){
		seg[ni<<1].sc += seg[ni].sc;
		seg[ni<<1|1].sc += seg[ni].sc;
	}
	seg[ni].fr.fr += seg[ni].sc; seg[ni].fr.sc += seg[ni].sc;
	seg[ni].sc = 0;
}
void upd(int ni, int ns, int ne, int qs, int qe, int qx){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return; }
	if (qs <= ns && ne <= qe){ seg[ni].sc += qx; return pro(ni, ns, ne); }
	int nm = ns+ne >> 1;
	upd(ni<<1, ns, nm, qs, qe, qx); upd(ni<<1|1, nm+1, ne, qs, qe, qx);
	seg[ni].fr.fr = min(seg[ni<<1].fr.fr, seg[ni<<1|1].fr.fr);
	seg[ni].fr.sc = max(seg[ni<<1].fr.sc, seg[ni<<1|1].fr.sc);
}
inline void upd(int st, int ed, int x){ return upd(1, 1, N, st, ed, x); }
pi2 qry(int ni, int ns, int ne, int qs, int qe){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return {INF, -INF}; }
	if (qs <= ns && ne <= qe){ return seg[ni].fr; }
	int nm = ns+ne >> 1;
	pi2 p1 = qry(ni<<1, ns, nm, qs, qe), p2 = qry(ni<<1|1, nm+1, ne, qs, qe);
	return { min(p1.fr, p2.fr), max(p1.sc, p2.sc) };
}
inline pi2 qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int t; cin >> t; while (t--){
		int n; cin >> n;
		for (int v = 2; v <= n; v++){ int w; cin >> w; adj[w].push_back(v); }
		dfs(1, -1);
		for (int i = 1; i <= n; i++){ int idx = ord[i].fr;
			int x; cin >> x; seg[N-1+idx].fr = {x, x};
		}
		for (int i = N-1; i >= 1; i--){
			seg[i].fr.fr = min(seg[i<<1].fr.fr, seg[i<<1|1].fr.fr);
			seg[i].fr.sc = max(seg[i<<1].fr.sc, seg[i<<1|1].fr.sc);
		}
		int q; cin >> q; while (q--){
			char typ; cin >> typ;
			if (typ == 'Q'){
				int v; cin >> v; pi2 res = qry(ord[v].fr, ord[v].sc);
				cout << res.sc - res.fr << endl;
			}
			if (typ == 'R'){
				int v, x; cin >> v >> x; upd(ord[v].fr, ord[v].sc, x);
			}
		}
		for (int i = 1; i < N+N; i++){ seg[i] = { {0, 0}, 0 }; }
		for (int i = 1; i <= n; i++){ ord[i] = {0, 0}; adj[i].clear(); } cnt = 0;
	}
}

D. [15899] 트리와 색깔 (Platinum II)

서브트리에 대한 쿼리에다가, 뭔가 Merge Sort Tree 기본형이 섞인듯한 문제입니다.

실제로도 그렇고, Euler Tour Technique로 트리를 수열로 변형시킨 뒤

그 수열을 기준으로 Merge Sort Tree를 구축하고

Subtree 쿼리가 들어올 때마다 구간에 맞게 이진 탐색으로 답을 찾아주면 됩니다.

int col[200020];
vector<int> adj[200020];

pi2 ord[200020]; int cnt = 0;
void dfs(int now, int pre){
	cnt += 1; ord[now].fr = cnt;
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
	ord[now].sc = cnt;
}

const int N = 262144; vector<int> seg[524290];
int qry(int st, int ed, int k){ st += N-1; ed += N-1;
	int res = 0;
	while (st <= ed){
		if (st & 1){ res += upper_bound(all(seg[st]), k) - seg[st].begin(); st += 1; }
		if (~ed & 1){ res += upper_bound(all(seg[ed]), k) - seg[ed].begin(); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

const int mod = 1e9 + 7;
void Main(){
	int n, q, _; cin >> n >> q >> _;
	for (int i = 1; i <= n; i++){ cin >> col[i]; }
	for (int i = 1; i < n; i++){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	dfs(1, -1);
	for (int i = 1; i <= n; i++){ int idx = ord[i].fr;
		seg[N-1+idx].push_back(col[i]);
	}
	for (int i = N-1; i >= 1; i--){
		seg[i].resize(seg[i<<1].size() + seg[i<<1|1].size());
		merge(all(seg[i<<1]), all(seg[i<<1|1]), seg[i].begin());
	}
	int ans = 0;
	while (q--){
		int v, c; cin >> v >> c;
		ans += qry(ord[v].fr, ord[v].sc, c); ans %= mod;
	}
	cout << ans;
}

E. [14446] Promotion Counting (Platinum II)

서브트리에 있는 정점들 중 나보다 더 큰 수를 가지고 있는 정점들의 개수를 세야 합니다.

일단 서브트리는 처리하기 귀찮으니, Euler Tour Technique를 사용해서 수열로 변환시켜봅시다.

 

그럼 각 정점별로 계산해야 하는 값은

자기 자신의 서브트리에서 → 어떠한 구간에서

나보다 더 큰 수를 가진 정점 개수 구하기 → 어떤 수보다 더 큰 수의 개수 구하기

가 됩니다.

 

어떤 구간에서 특정 수보다 더 큰 수의 개수를 구하는 건 이미 여러 번 해봤으니,

Merge Sort Tree를 짜고 계산해주면 됩니다.

vector<int> adj[100020];
int arr[100020];

pi2 ord[100020]; int num = 0;
void dfs(int now, int pre){
	num += 1; ord[now].fr = num;
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
	ord[now].sc = num;
}

const int N = 131072;
vector<int> seg[262150];
int qry(int st, int ed, int val){ st += N-1; ed += N-1;
	int res = 0;
	while (st <= ed){
		if (st & 1){ res += seg[st].end() - upper_bound(all(seg[st]), val); st += 1; }
		if (~ed & 1){ res += seg[ed].end() - upper_bound(all(seg[ed]), val); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int v = 2; v <= n; v++){ int w; cin >> w; adj[w].push_back(v); }
	dfs(1, -1);
	for (int i = 1; i <= n; i++){
		int idx = ord[i].fr;
		seg[idx+N-1].push_back(arr[i]);
	}
	for (int i = N-1; i >= 1; i--){
		seg[i].resize(seg[i<<1].size() + seg[i<<1|1].size());
		merge(all(seg[i<<1]), all(seg[i<<1|1]), seg[i].begin());
	}
	for (int i = 1; i <= n; i++){ cout << qry(ord[i].fr, ord[i].sc, arr[i]) << endl; }
}