2021년 1월 20일 PS 일지

1. Segment Tree 연습문제 마무리

2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest

C. Component Tree

codeforces.com/gym/100513/problem/C

Problem - C - Codeforces

 

분명 간단한 세그트리 연습문제라 들었건만 정말 어렵다

2시간 이상 고민했는데 풀이가 안 나와서 풀이를 찾아봤다. 정말 다양한 풀이를 봤지만 이해가 안됨.

오히려 HLD 쓰는 풀이를 이해해버려서 세그 쓰는 풀이를 탐색 중임.

 

그냥 혼자 생각하기로 함.

일단 property 별로 생각하는 것은 명백하다. 

어떤 노드가 property를 가지고 있다. -> 자신의 subtree에 영향을 미친다.

결국 구간을 업데이트한다고 생각할 수 있다. (벽칠하기 느낌)

이때 중요한 건 구간은 log N개의 세그 트리 구간으로 쪼갤 수 있다.

그럼 각 구간마다 맵을 하나씩 만들고 property 당 value를 저장한다.

이때 깊이가 더 깊은 노드의 업데이트가 최종적으로 반영되도록 업데이트를 진행한다. dfs를 두 번 돌려도 되고 dfs 한 번 돌릴 때 업데이트를 똑똑하게 해도 된다.

 

구간 업데이트 -> 포인트 쿼리라고 생각하면 될듯

어떤 포인트의 property의 값을 아는 방법은 아래서부터 쭉 올라가다가 propery의 값을 가진 map을 만나는 순간 바로 그 값을 리턴하면 된다. 개인적으로 정말 인상깊은 문제다. 세그가 이렇게 어려울 수도 있다는 사실을 깨달음.

 

시간이 ㄷㄷ 

참고로 시간제한이 6초다.

꽤 잘 짰다고 생각해서 코드를 올린다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Seg{
	int st;
	vector<map<string,string>> tree;
	Seg(int k=0){
		st = 1<<(int)ceil(log2(k));
		tree.resize(2*st);
	}
	void update(int l,int r,const string&prop,string&v){
		for(l+=st,r+=st;l<=r;l>>=1,r>>=1){
			if(l&1){
				if(tree[l].count(prop)==0)
					tree[l][prop] = v;
				l++;
			}
			if(!(r&1)){
				if(tree[r].count(prop)==0)
					tree[r][prop] = v;
				r--;
			}
		}
	}
	string query(int p,const string&prop){
		for(p+=st;p>0;p>>=1){
			if(tree[p].count(prop)>0){
				return tree[p][prop];
			}
		}
		return "N/A";
	}
}f;
const int N = 3e5+5;
int in[N],pv,par[N],sz[N];
vector<int> g[N];
map<string,string> mp[N];
void dfs(int k=1){
	in[k] = pv++;
	sz[k] = 1;
	for(int nxt:g[k]){
		dfs(nxt);
		sz[k] += sz[nxt];
	}
	for(auto&[key,val]:mp[k])
		f.update(in[k],in[k]+sz[k]-1,key,val);
}
int main(){
    // ios::sync_with_stdio(!cin.tie(0));
    int n; scanf("%d",&n);
	f = Seg(n);
	char key[15],val[15];
	for(int i=1,p;i<=n;i++){
		scanf("%d %d",par+i,&p);
		g[par[i]].push_back(i);
		while(p--){
			scanf(" %[^=]=%s",key,val);
			mp[i][string(key)] = string(val);
		}
	}
	dfs();
	int Q; scanf("%d",&Q);
	while(Q--){
		int k; scanf("%d %s",&k,key);
		printf("%s\n",f.query(in[k],string(key)).c_str()); fflush(stdout);
	}
}

여담으로 map<string,string> mp을 만드는 것보다

string 배열을 하나 만들어놓고

세그트리에 map<string,int>를 박는게 훨씬 효율적이겠다. string을 들고 다닌 것보다 효율적.

 

2. Persistence Segment Tree 공부

2021/01/18 - [Problem Solving/알고리즘 이론 정리] - Persistent Segment Tree 구현 메모

 

내용 정리는 아니고, 공부한 글들과 내 구현을 메모해 놓는다.