고급반 2주차 풀이 - 두근두근

1. [20295] 사탕 배달 (Platinum III)

사탕의 종류가 5개밖에 없으니, Bitmask와 Sparse Table을 사용해서 \( v \)의 \( 2^{j} \)번째 조상과 그 경로에 있는 캔디의 종류들을 저장할 수 있습니다.

 

이제 쿼리를 처리해봅시다.

현재 내가 있는 정점이 \( v \)이고 친구가 있는 정점이 \( w \)이며, 친구는 \( k \)번 종류의 사탕을 원한다고 합니다.

 

최단경로로 이동해야 하므로, \( l = LCA(v, w) \)라고 할 때 \( v \rightarrow l \rightarrow w \)의 경로로 이동해야 합니다. 즉, \( v \rightarrow l \) 또는 \( w \rightarrow l \)의 경로에 \( k \)번 종류의 사탕이 있는지만 판별해주면 되고, 쿼리당 \( O(\log N) \)의 시간, 총 \( O((N+Q) \log N) \)의 시간에 문제를 해결할 수 있습니다.

const int N = 20;
int arr[100020];
vector<int> adj[100020];
pi2 spr[100020][22];
bool chk[6];

int dep[100020];
void dfs(int now, int pre){
	dep[now] = dep[pre]+1;
	spr[now][0] = {pre, (1<<arr[now]) | (1<<arr[pre])};
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
}

pi2 lca(int a, int b){
	if (dep[a] > dep[b]){ swap(a, b); }
	int da = dep[a], db = dep[b]; int dif = db - da;
	int bit = (1<<arr[a]) | (1<<arr[b]);
	for (int j = N; j >= 0; j--){
		if (dif & 1<<j){ bit |= spr[b][j].sc; b = spr[b][j].fr; }
	}
	if (a == b){ return {a, bit}; }
	for (int j = N; j >= 0; j--){
		if (spr[a][j].fr != spr[b][j].fr){
			bit |= spr[a][j].sc; a = spr[a][j].fr;
			bit |= spr[b][j].sc; b = spr[b][j].fr;
		}
	}
	bit |= spr[a][0].sc | spr[b][0].sc;
	return { spr[a][0].fr, bit };
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; chk[ arr[i] ] = 1; }
	for (int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dfs(1, 1);
	for (int j = 1; j <= N; j++){
		for (int i = 1; i <= n; i++){
			spr[i][j].fr = spr[ spr[i][j-1].fr ][j-1].fr;
			spr[i][j].sc = spr[i][j-1].sc | spr[ spr[i][j-1].fr ][j-1].sc;
		}
	}
	int q; cin >> q;
	int ptr = -1;
	while (q--){
		int a, b; cin >> a >> b;
		if (ptr == -1){
			if (!chk[b]){ cout << "CRY" << endl; }
			else{ cout << "PLAY" << endl; }
			ptr = a; continue;
		}
		if (ptr == a){
			if (arr[a] != b){ cout << "CRY" << endl; }
			else{ cout << "PLAY" << endl; }
			continue;
		}
		pi2 p = lca(ptr, a);
		if (p.sc & 1<<b){ cout << "PLAY" << endl; }
		else{ cout << "CRY" << endl; }
		ptr = a;
	}
}

2. [17227] 그래서 팩 주냐? (Platinum III)

게임이론 같기도 하고, DP같기도 한 이 문제는 게임이론 + DP로 푸는 문제입니다.

 

\( DP_{i,0} := \) "만영이가 \( i \)번 주제에서 주제를 고를 차례"일 때, 준표가 추가적으로 정색해야 하는 횟수

\( DP_{i,1} := \) "준표가 \( i \)번 주제에서 주제를 고를 차례"일 때, 준표가 추가적으로 정색해야 하는 횟수

 

초항을 \( DP_{N, 0} = \infty \), DP_{N, 1} = 0 \)으로 잡고 시작합시다.

즉, 만영이가 \( N \)번 주제를 고르는 일이 절대 발생하지 않도록 준표가 \( \infty \)회만큼 정색하게 하는 것입니다.

 

이제 간선을 뒤집은 뒤, 위상정렬을 돌리고 그 순서대로 DP를 전파시켜봅시다.

간선을 뒤집었기 때문에, \( v \)를 탐색할 때에는 항상 원래 그래프에서 \( v \rightarrow w \)인 모든 \( w \)의 계산이 완료된 상태가 됩니다.

이제 본격적으로 \( v \)번 주제에서의 준표와 만영이의 행동을 분석해봅시다.

편의상 다음 주제는 \( w \)번 주제라고 하겠습니다.

 

준표의 행동은 어렵지 않습니다. "만영이가 \( w \)번 주제에서 선택을 시작할 때 준표의 정색 횟수"를 최소화해야 하므로, \( \min_{v \rightarrow w} DP_{w, 0} \)가 됩니다.

 

만영이의 행동은 다음과 같습니다.

결론부터 말하자면, 만영이는 \( DP_{w, 0} \)이 큰 주제부터 하나하나씩 시도를 시작합니다.

그럼 이 때 준표의 행동은 저 DP값과 여기서 정색하는 횟수의 합이 최소화가 되는 시점에서 정색을 멈추게 됩니다.

즉, 준표의 정색 횟수는 \( \min (DP_{w, 0} + \text{position of }w) \)가 됩니다.

 

DP 계산이 끝난 뒤에는, 각 시작 화제별로 \( DP_{v, 1} \)을 본 뒤, 가장 작은 값을 선택해주면 됩니다. 이 값이 \( \infty \)일 때는 -1을 출력해야 함에 유의하세요.

 

시간복잡도는 \( O(N) \)입니다.

const ll INF = 1e15;
vector<int> adj[100020], jda[100020]; int nxc[100020];
bool st[100020];
pl2 dp[100020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ st[i] = 1; }
	for (int i = 1; i <= m; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); st[b] = 0;
		jda[b].push_back(a); nxc[a] += 1;
	}
	queue<int> q; q.push(n);
	while (!q.empty()){
		int now = q.front(); q.pop();
		for (int pre : jda[now]){
			nxc[pre] -= 1;
			if (nxc[pre] == 0){ q.push(pre); }
		}
		vector<ll> v1, v2;
		for (int nxt : adj[now]){
			v1.push_back(dp[nxt].sc); v2.push_back(dp[nxt].fr);
		}
		sort( all(v1) ); sort( all(v2), [](ll a, ll b){ return a > b; } );
		ll mn1 = INF, mn2 = INF;
		for (ll x1 : v1){ mn1 = min(mn1, x1); }
		int cnt = 0;
		for (ll x2 : v2){ mn2 = min(mn2, x2+cnt); cnt += 1; }
		if (now == n){ dp[now] = {INF, 0}; }
		else{ dp[now] = {mn1, mn2}; }
		//cout << "DP " << now << " = " << dp[now].fr << ' ' << dp[now].sc << endl;
	}
	ll ans = INF;
	for (int i = 1; i <= n; i++){
		if (!st[i]){ continue; }
		ans = min(ans, dp[i].sc);
	}
	if (ans == INF){ cout << -1; } else{ cout << ans; }
}

3. [20039] Coronavirus Trend (Platinum III)

우선 길이가 \( N-1 \)인 Difference 배열을 만든 뒤 생각해봅시다.

Difference 배열을 통해 문제를 재정의하면, 이 Difference 배열에서 값을 적절히 합쳐서 isolated된 +와 -가 없도록 만드는 문제가 됨을 볼 수 있습니다. (문제의 조건에 의해 0은 나올 수 없습니다.)

여기서부터는 "\( A \) 배열 = Difference 배열" 입니다.

 

이제 이를 DP로 풀어봅시다.

\( DP_{i, s, c} := \) \( A \)의 첫 \( i \)개의 수만 생각해봤을 때, 마지막에 부호가 \( sgn \)인 수가 \( c \)회 연속으로 나오게 하기 위해 필요한 합치기의 최소 횟수

+ 문제 특성상 \( c \ge 2 \)인 경우를 그냥 \( c = 2 \)에 저장해줘도 별 문제 없습니다.

 

이제 점화식을 세워봅시다. (편의상 \( s = + \)인 경우만 보여주겠습니다. \( s = - \)인 경우는 +와 -를 바꿔주면 됩니다.)

\( c = 1 \)인 경우: 다른 부호였다가 이 부호로 오는 경우 또는 0 (선택한 값이 없었음)에서 이 부호로 오는 경우입니다. 주의할 점은, (다른 부호, 1회 선택)은 선택하면 안 됩니다.

\( c = 2 \)인 경우: 같은 부호의 개수를 늘리는 경우입니다.

 

식으로 적자면

\( DP_{i, +, 1} = \min_{A_{(j,i]} \gt 0} (DP_{j, -, 2} + i-j) \) / \( DP_{i, +, 1} = i-1 \text{ if } A_{[1, i]} \gt 0 \text{ else } \infty \) 중 더 작은 값

\( DP_{i, +, 2} = \min_{A_{(j, i]} \gt 0} (\min(DP_{j, +, 1}, DP_{j, +, 2}) + i-j) \)

 

그런데 이대로 구현하면 \( O(N^2) \)의, TLE를 받기 좋은 시간복잡도가 됩니다.

그러니 '세그먼트 트리로 DP를 최적화'해주면 됩니다.

 

각 \( s, c \)별로 세그먼트 트리를 따로 만들어준 뒤,

각각의 세그먼트 트리의 \( i \)번째 자식에 \( DP_{i, s, c} \)를 저장해주면, 점화식을 Range Minimum Query를 통해 \( O(\log N) \)의 시간만에 구할 수 있게 됩니다.

 

이제 시간복잡도는 \( O(N \log N) \)이 되었으니, 구현에 들어가면 됩니다.

int arr[500020], dif[500020];
map<int, int> cvt; set<int> cs; int cc = 0;

const int INF = 1e9;
const int N = 524288; int seg[3][2][1048576];
void upd(int sgn, int cnt, int pos, int val){ cnt -= 1; pos += N-1;
	seg[sgn][cnt][pos] = val; pos >>= 1;
	while (pos){
		seg[sgn][cnt][pos] = max(seg[sgn][cnt][pos<<1], seg[sgn][cnt][pos<<1|1]);
		pos >>= 1;
	}
}
int qry(int sgn, int cnt, int st, int ed){ cnt -= 1; st += N-1; ed += N-1;
	int res = -INF;
	while (st <= ed){
		if (st & 1){ res = max(res, seg[sgn][cnt][st]); st += 1; }
		if (~ed & 1){ res = max(res, seg[sgn][cnt][ed]); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n; cin >> n;
	for (int i = 0; i < n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
	for (int x : cs){ cc += 1; cvt[x] = cc; }
	for (int i = 0; i < n; i++){ arr[i] = cvt[ arr[i] ]; }
	for (int i = 1; i < n; i++){ dif[i] = arr[i] - arr[i-1]; }
	//for (int i = 1; i < n; i++){ cout << dif[i] << ' '; } cout << endl;
	for (int i : {0, 1, 2}){ for (int j : {0, 1}){ for (int k = 1; k < N+N; k++){ seg[i][j][k] = -INF; } } }
	for (int i = 1; i < n; i++){
		upd(0, 1, arr[i-1], 1);
		for (int sgn : {1, 2}){
			int st = sgn==1 ? arr[i]+1 : 1; int ed = sgn==1 ? N : arr[i]-1;
			int r1 = max({ qry(3-sgn, 2, st, ed), qry(0, 1, st, ed) });
			int r2 = max({ qry(sgn, 1, st, ed), qry(sgn, 2, st, ed) });
			upd(sgn, 1, arr[i], r1+1); upd(sgn, 2, arr[i], r2+1);
			//cout << "DP " << arr[i] << ' ' << sgn << ' ' << 1 << " = " << r1+1 << endl;
			//cout << "DP " << arr[i] << ' ' << sgn << ' ' << 2 << " = " << r2+1 << endl;
		}
		//cout << endl;
	}
	int ans = max( qry(1, 2, 1, N), qry(2, 2, 1, N) );
	cout << max(ans, 0);
}

4. [6091] 핑크 플로이드 (Platinum V)

\( v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{k} \)라고 하면, \( v_{0} \rightarrow v_{k} \)의 경로는 위에 나온 간선들보다 더 큰 값이 될 수밖에 없습니다.

이를 모든 사이클에 잘 적용시키면, 결국 이 문제가 Minimum Spanning Tree를 구하는 문제임을 알아차릴 수 있습니다.

불가능한 경우 같은 것도 없으니 편하게 구현해주면 됩니다.

 

시간복잡도는 \( O(N^2) \)입니다.

priority_queue< pi3, vector<pi3>, greater<pi3> > pq;
vector<int> adj[1030];

int par[1030];
int fnd(int a){ return par[a] = par[a] == a ? a : fnd(par[a]); }
void uni(int a, int b){ par[fnd(a)] = fnd(b); }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	for (int i = 1; i <= n; i++){
		for (int j = i+1; j <= n; j++){
			int x; cin >> x;
			pq.push({ x, {i, j} });
		}
	}
	while (!pq.empty()){
		int dis = pq.top().fr;
		int v = pq.top().sc.fr, w = pq.top().sc.sc;
		pq.pop();
		if ( fnd(v) == fnd(w) ){ continue; } uni(v, w);
		adj[v].push_back(w); adj[w].push_back(v);
	}
	for (int i = 1; i <= n; i++){
		sort( all(adj[i]) );
		cout << adj[i].size() << ' ';
		for (int x : adj[i]){ cout << x << ' '; } cout << endl;
	}
}

5. [2401] 최대 문자열 붙여넣기 (Platinum II)

짧은 문자열이 1개만 주어진다면, 아래와 같이 DP를 돌릴 수 있습니다.

\( DP_{i} := \) 긴 문자열의 첫 \( i \)글자만 봤을 때의 답

 

점화식은 두 경우로 나눠서 처리할 수 있습니다.

1. \( i \)번째 글자를 매칭하지 않는 경우: \( DP_{i-1} \)

2. \( i \)번째 글자를 매칭하는 경우: \( (j, i] \) 구간에서 매칭이 발생했다고 하면, \( DP_{j} + l \)

둘 중 더 큰 값을 선택하면 됩니다.

 

그런데 이 문제에서는 문자열이 500개 주어지니까, KMP 500개를 동시에 돌리면서 2번 경우가 발생할 때마다 \( DP_{j} + l_{k} \)를 계산해주면 됩니다.

 

초항은 \( DP_{0} = 0 \)이고, 문제의 답은 \( DP_{L} \)입니다.

시간복잡도는 \( O(LM) \)입니다.

string arr[520];
int jmp[520][10020], len[520], pos[520];
int dp[100020];

void Main(){
	string s; cin >> s; int sl = s.size(); s = " " + s;
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		string& str = arr[i]; cin >> str; int l = str.size();
		len[i] = l;
		int ptr = 0;
		for (int si = 1; si < l; si++){
			while (ptr != 0 && str[ptr] != str[si]){ ptr = jmp[i][ptr-1]; }
			if (str[ptr] == str[si]){ ptr += 1; }
			jmp[i][si] = ptr;
		}
	}
	for (int i = 1; i <= sl; i++){
		dp[i] = dp[i-1];
		for (int j = 1; j <= n; j++){
			while (pos[j] != 0 && arr[j][ pos[j] ] != s[i]){ pos[j] = jmp[j][ pos[j]-1 ]; }
			if (arr[j][ pos[j] ] == s[i]){ pos[j] += 1; }
			//cout << "IJ " << i << ' ' << j << " -> " << pos[j] << endl;
			if (pos[j] == len[j]){
				int st = i-len[j];
				dp[i] = max(dp[i], dp[st] + len[j]);
				pos[j] = jmp[j][ pos[j]-1 ];
			}
		}
	}
	cout << dp[sl];
}

6. [12895] 화려한 마을 (Platinum III)

색상의 종류 \( T \)가 30개밖에 되지 않습니다. Bitmask를 쓰라는 계시죠.

거기에다가 Range Update & Range Query니 Segment Tree with Lazy Propagation까지 쓰면 됩니다.

 

세그먼트 트리의 각 정점에 '그 구간에서 보이는 색상'을 비트마스크로 저장하면, 두 쿼리를 다음과 같이 처리할 수 있습니다.

1. \( [x, y] \) 구간의 집을 \( z \)번 색으로 칠하기: \( [x, y] \) 구간을 \( 2^{z} \)로 바꿔주면 됩니다. 물론 Range Update니 Lazy하게 바꿔야 하지만요.

2. \( [x, y] \) 구간에 존재하는 색깔의 종류: \( [x, y] \) 구간에 속하는 정점들을 모두 Bitwise OR 해준 뒤, 켜진 비트의 개수를 세주면 됩니다.

 

시간복잡도는 \( O(N + Q \log N) \)입니다.

const int N = 131072; pi2 seg[262150];
void pro(int nod, int ns, int ne){
	if (seg[nod].sc == 0){ return; }
	seg[nod].fr = seg[nod].sc;
	if (ns != ne){
		seg[nod<<1].sc = seg[nod].sc;
		seg[nod<<1|1].sc = seg[nod].sc;
	}
	seg[nod].sc = 0;
}
void upd(int nod, int ns, int ne, int st, int ed, int val){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){ seg[nod].sc = val; return pro(nod, ns, ne); }
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, val); upd(nod<<1|1, mid+1, ne, st, ed, val);
	int x1 = seg[nod<<1].sc==0 ? seg[nod<<1].fr : seg[nod<<1].sc;
	int x2 = seg[nod<<1|1].sc==0 ? seg[nod<<1|1].fr : seg[nod<<1|1].sc;
	seg[nod] = {x1 | x2, 0};
}
void upd(int st, int ed, int val){ return upd( 1, 1, N, st, ed, 1<<(val-1) ); }
int qry(int nod, int ns, int ne, int st, int ed){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return 0; }
	if (st <= ns && ne <= ed){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	return qry(nod<<1, ns, mid, st, ed) | qry(nod<<1|1, mid+1, ne, st, ed);
}
int qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < N+N; i++){ seg[i] = {1, 0}; }
	while (q--){
		char m; cin >> m;
		if (m == 'C'){
			int st, ed, col; cin >> st >> ed >> col;
			if (st > ed){ swap(st, ed); }
			upd(st, ed, col);
		}
		if (m == 'Q'){
			int st, ed; cin >> st >> ed;
			if (st > ed){ swap(st, ed); }
			int res = qry(st, ed);
			int cnt = 0; while (res){ cnt += 1; res -= res&-res; }
			cout << cnt << endl;
		}
	}
}

7. [2336] 굉장한 학생 (Platinum II)

우선 \( i \)번 학생이 받은 3개의 순위를 각각 \( A_{i}, B_{i}, C_{i} \)라고 합시다.

3개를 다 다루는 건 힘들고 귀찮은 작업이니, 고려해야 하는 순위를 하나하나씩 없애줍시다.

 

우선 \( A \)는 간단히 없애줄 수 있습니다. 학생들을 \( A \)를 기준으로 정렬시킨 뒤, 각 학생별로 자기 자신보다 더 앞에 있는 사람들만 고려하게 해두면 됩니다.

 

이제 \( B \)와 \( C \)만 남았는데, 이는 세그먼트 트리를 사용해서 처리할 수 있습니다.

\( i \)번 학생은 세그먼트 트리의 \( B_{i} \)번째 정점에 \( C_{i} \)위를 저장하도록 놓으면,

\( A_{i} \lt A_{j} \)인 어떤 \( j \)번 학생이 \( B_{j}, C_{j} \)의 성적을 받았을 때

\( [1, B_{j}) \) 구간에 \( C_{i} \lt C_{j} \)인 학생이 존재하는지 판별해주면 됩니다.

 

즉 \( A \)는 정렬 기준에 넣고, \( B \)는 세그먼트 트리의 정점으로 넣은 뒤, \( C \)는 Range Minimum Query의 인자로 넣어주면 됩니다.

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

pi3 arr[500020];
void Main(){
	for (int i = 1; i < N+N; i++){ seg[i] = INF; }
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].fr = i; }
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].sc.fr = i; }
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].sc.sc = i; }
	sort(arr+1, arr+n+1);
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int r1 = arr[i].fr, r2 = arr[i].sc.fr, r3 = arr[i].sc.sc;
		int mnr = qry(1, r2);
		if (mnr > r3){ ans += 1; }
		upd(r2, r3);
	}
	cout << ans;
}

8. [17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (Platinum II)

Range Update & Point Query입니다.

그런데 Range Update의 상태가 이상한데...

 

만약 세그트리에 그냥 값을 저장하는 대신 \( ax + b \)를 저장하도록 시킨 뒤,

실제 별의 개수를 구할 때 \( x \)에 자신의 위치 번호를 넣도록 시킨다면,

Range Update를 다음과 같이 쓸 수 있습니다.

\( [L, R] \) 구간에 \( x - (L-1) \)개의 별이 떨어진다.

 

그러니 저렇게 Segment Tree with Lazy Propagation을 짜면 됩니다.

 + 초깃값은 \( 0x + A_{i} \)로 저장하면 됩니다.

 

시간복잡도는 \( O(N \log N) \)입니다.

const int N = 131072; pl4 seg[262150];
void pro(int nod, int ns, int ne){ int cnt = ne-ns + 1;
	seg[nod].fr.fr += seg[nod].sc.fr * cnt;
	seg[nod].fr.sc += seg[nod].sc.sc * cnt;
	if (ns != ne){
		seg[nod<<1].sc.fr += seg[nod].sc.fr;
		seg[nod<<1].sc.sc += seg[nod].sc.sc;
		seg[nod<<1|1].sc.fr += seg[nod].sc.fr;
		seg[nod<<1|1].sc.sc += seg[nod].sc.sc;
	}
	seg[nod].sc = {0, 0};
}
void upd(int nod, int ns, int ne, int st, int ed, pl2 val){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){
		seg[nod].sc.fr += val.fr; seg[nod].sc.sc += val.sc;
		return pro(nod, ns, ne);
	}
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, val); upd(nod<<1|1, mid+1, ne, st, ed, val);
	seg[nod].sc.fr = seg[nod<<1].sc.fr + seg[nod<<1|1].sc.fr;
	seg[nod].sc.sc = seg[nod<<1].sc.sc + seg[nod<<1|1].sc.sc;
}
void upd(int st, int ed, pl2 val){ return upd(1, 1, N, st, ed, val); }
pl2 qry(int nod, int ns, int ne, int pos){
	pro(nod, ns, ne);
	if (pos < ns || ne < pos){ return {0, 0}; }
	if (pos <= ns && ne <= pos){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	pl2 r1 = qry(nod<<1, ns, mid, pos), r2 = qry(nod<<1|1, mid+1, ne, pos);
	return {r1.fr+r2.fr, r1.sc+r2.sc};
}
pl2 qry(int pos){ return qry(1, 1, N, pos); }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ int x; cin >> x; upd(i, i, {0, x}); }
	int q; cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){ int st, ed; cin >> st >> ed; upd(st, ed, {1, -st+1}); }
		if (m == 2){
			int pos; cin >> pos;
			pl2 res = qry(pos);
			cout << res.fr*pos + res.sc << endl;
		}
	}
}

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

문제에서 요구하는 건 Subtree Add Update & Vertex Query입니다.

 

Euler Tour Technique을 사용하면 Subtree Update를 Range Update로 바꿀 수 있으니, 이를 써주면

Range Add Update & Point Query가 됩니다.

 

Range Add Update & Point Query는 세그트리에 Difference 배열을 섞어주면

Point Add Update & Range Sum Query로 고칠 수 있습니다.

 

이제 코드를 짜기 쉬워졌으니 저대로 짜주면 됩니다.

시간복잡도는 \( O(N \log N) \)입니다.

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;
		}
	}
}

10. [17407] 괄호 문자열과 쿼리 (Platinum II)

어떤 문자열 \( S \)가 괄호 문자열이라는 건 다음과 동치입니다.

'('를 \( +1 \)로, ')'를 \( -1 \)로 변환한 뒤, 이를 \( A_{i} \)라고 하자.

\( A_{i} \)의 누적합을 저장하는 배열을 \( B_{i} = \sum_{k=1}^{i} A_{k} \)라고 할 때, \( B_{N} = 0 \)이면서 \( \min_{1 \le i \le N} B_{i} = 0 \)이다.

\( B_{N} \)을 따로 저장해둔다면, \( \min_{1 \le i \le N} B_{i} \)만 알면 됩니다.

 

그런데 '('와 ')'를 바꾸는 쿼리 역시 처리해줘야 하니, Range Add Update & Range Minimum Query를 해야 합니다.

\( S_{i} \)를 '('에서 ')'로 바꿀 때: \( [i, N] \) 구간의 \( B_{i} \)에 2씩 빼기

\( S_{i} \)를 ')'에서 '('로 바꿀 때: \( [i, N] \) 구간의 \( B_{i} \)에 2씩 더하기

괄호 문자열 판별: \( B_{N} = 0 \)이고 \( \min_{1 \le i \le N} B_{i} = 0 \)

이는 Segment Tree with Lazy Propagation을 통해 해결할 수 있습니다.

 

\( B_{N} \)을 따로 저장해둬야 하니, 위 쿼리를 처리하면서 \( B_{N} \)도 같이 업데이트해야 함에 주의하세요.

 

시간복잡도는 \( O(N \log N) \)입니다.

const int N = 131072, INF = 1e9; pi2 seg[262150];
void pro(int nod, int ns, int ne){
	seg[nod].fr += seg[nod].sc;
	if (ns != ne){
		seg[nod<<1].sc += seg[nod].sc;
		seg[nod<<1|1].sc += seg[nod].sc;
	}
	seg[nod].sc = 0;
}
void upd(int nod, int ns, int ne, int st, int ed, int dif){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){ seg[nod].sc += dif; return pro(nod, ns, ne); }
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, dif); upd(nod<<1|1, mid+1, ne, st, ed, dif);
	int x1 = seg[nod<<1].fr + seg[nod<<1].sc;
	int x2 = seg[nod<<1|1].fr + seg[nod<<1|1].sc;
	seg[nod] = {min(x1, x2), 0};
}
void upd(int st, int ed, int dif){ return upd(1, 1, N, st, ed, dif); }
int qry(int nod, int ns, int ne, int st, int ed){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return INF; }
	if (st <= ne && ne <= ed){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	return min( qry(nod<<1, ns, mid, st, ed), qry(nod<<1|1, mid+1, ne, st, ed) );
}
int qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	for (int i = 1; i < N+N; i++){ seg[i] = {INF, 0}; }
	string s; cin >> s; int n = s.size(); s = " " + s;
	int sum = 0;
	for (int i = 1; i <= n; i++){
		if (s[i] == '('){ sum += 1; } else{ sum -= 1; }
		seg[i+N-1] = {sum, 0};
	}
	for (int i = N-1; i >= 1; i--){
		seg[i] = { min(seg[i<<1].fr, seg[i<<1|1].fr), 0 };
	}
	int ans = 0;
	int q; cin >> q;
	while (q--){
		int pos; cin >> pos;
		if (s[pos] == '('){ sum -= 2; upd(pos, n, -2); }
		else{ sum += 2; upd(pos, n, 2); }
		//cout << "QRY " << sum << ' ' << qry(1, n) << endl;
		if (sum == 0 && qry(1, n) == 0){ ans += 1; }
		s[pos] ^= '('^')';
	}
	cout << ans;
}

11. [10167] 금광 (Diamond V)

Well-known 금광 세그 (Maximum Subsegment Sum Segment Tree)의 고향입니다.

 

금광 세그를 요약하자면, 특정 구간에서의 최대 연속합을 구하는 세그먼트 트리로, 다음 4가지 정보를 저장합니다.

\( prf := \) 앞에서부터 더할 때의 최대 연속합

\( suf := \) 뒤에서부터 더할 때의 최대 연속합

\( tot := \) 구간 내의 모든 원소의 합

\( res := \) 구간 내의 최대 연속합

 

그리고 \( w_{1} \)과 \( w_{2} \)를 자식으로 가지고 있는 \( v \)의 정보는 다음과 같이 계산됩니다.

\( prf_{v} = \max (prf_{w_{1}}, tot_{w_{1}} + prf_{w_{2}}) \)

\( suf_{v} = \max (suf_{w_{1}} + tot_{w_{2}}, suf_{w_{2}}) \)

\( tot_{v} = tot_{w_{1}} + tot_{w_{2}} \)

\( res_{v} = \max (res_{w_{1}}, res_{w_{2}}, suf_{w_{1}} + prf_{w_{2}}) \)

 

이제 금광 문제를 풀어봅시다.

우선 점을 y좌표로 정렬한 뒤, 직사각형의 위와 아래를 정의하는 두 직선 y1과 y2를 고정해봅시다.

그럼 그 때 우리가 얻을 수 있는 최대 이익은 이렇게 구할 수 있습니다.

y좌표가 y1 ~ y2인 점들만 들고 올 때,

이 점들을 x좌표를 기준으로 정렬한 뒤,

같은 x좌표를 가진 점들은 그냥 합해버리고,

최대 연속합을 찾아주면 됩니다.

 

이 과정을 그냥 하는 건 아마 느릴테지만, 밑의 최대 연속합을 찾는 부분은 위에서 놓은 금광세그로 처리해버리면, y좌표가 y1 ~ y2인 점들을 필터링하는 부분밖에 남지 않습니다.

그럼 여기서 y1만 고정해봅시다. 원래 점이 y좌표 순으로 정렬되어있다고 하면, y = y1인 점부터 시작해서 점을 하나씩 추가해나가면 y2는 알아서 증가할테니, y1에 대해 가능한 "모든" y2에 대한 답을 스위핑으로 구할 수 있게 됩니다.

 

요약: 점을 y로 정렬 → y1을 고정 → 그걸로 y2를 스위핑 돌리면서 최대 연속합을 찾아줌

y1, y2를 선택할 때 'y1과 y2의 "모든" 점'이 들어가야 함에 주의하세요.

 

이제 시간복잡도를 구해보면 \( O(N \times N \log N) \)이 되니, 신나게 구현에 들어가면 됩니다.

const int N = 4096; pl4 seg[8200];
void upd(int pos, ll val){ pos += N-1;
	seg[pos].fr.fr += val;
	seg[pos].fr.sc += val;
	seg[pos].sc.fr += val;
	seg[pos].sc.sc += val;
	pos >>= 1;
	while (pos){
		int p1 = pos<<1, p2 = pos<<1|1;
		seg[pos].sc.fr = max(seg[p1].sc.fr, seg[p1].fr.sc + seg[p2].sc.fr);
		seg[pos].sc.sc = max(seg[p2].sc.sc, seg[p2].fr.sc + seg[p1].sc.sc);
		seg[pos].fr.sc = seg[p1].fr.sc + seg[p2].fr.sc;
		seg[pos].fr.fr = max({ seg[p1].fr.fr, seg[p2].fr.fr, seg[p1].sc.sc + seg[p2].sc.fr });
		pos >>= 1;
	}
}

map<int, int> cvt; set<int> cs; int cc = 0;
pl3 arr[3020];
void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i].fr.fr >> arr[i].fr.sc >> arr[i].sc;
		cs.insert(arr[i].fr.sc);
	}
	sort(arr+1, arr+n+1);
	for (int x : cs){ cc += 1; cvt[x] = cc; }
	for (int i = 1; i <= n; i++){ arr[i].fr.sc = cvt[ arr[i].fr.sc ]; }
	ll ans = 0;
	for (int i1 = 1; i1 <= n; i1++){
		if (i1 != 1 && arr[i1-1].fr.fr == arr[i1].fr.fr){ continue; }
		for (int i2 = i1; i2 <= n; i2++){
			upd(arr[i2].fr.sc, arr[i2].sc);
			if (i2 == n || arr[i2].fr.fr != arr[i2+1].fr.fr){
				ans = max(ans, seg[1].fr.fr);
			}
		}
		for (int i = 1; i < N+N; i++){ seg[i] = { {0, 0}, {0, 0} }; }
	}
	cout << ans;
}

12. [21340] Dragon Balls (Platinum V)

일단 아무 점 \( (y_{0}, x_{0}) \)이나 잡고 물어본 뒤 \( d_{0} \)를 받아봅시다.

그럼 거기서 거리가 정확히 \( d_{0}^{2} \)인 점들을 모아볼 수 있습니다.

이제 그 점들 중 아직 물어보지 않은 한 점 \( (y_{1}, x_{1}) \)을 잡고 물어본 뒤 \( d_{1} \)을 받고, 거리가 \( d_{1}^{2} \)보다 더 먼 점을 후보에서 없애봅시다.

이제 남은 점들 중 아직 물어보지 않은 한 점 \( (y_{2}, x_{2}) \)를 잡고 물어본 뒤 \( d_{2} \)를 받고, 거리가 \( d_{2}^{2} \)보다 더 먼 점을 후보에서 없애봅시다.

이런 식으로 가다가 \( d_{i} = 0 \)이 된 시점에서 하나를 찾았다고 표시한 뒤, 아직 더 찾을 게 있으면 위 과정을 반복하고, 아니면 종료하면 됩니다.

 

이게 왜 맞는지는 Proof by AC를 해주면 됩니다. [TODO: 증명]

const int N = 1'000'000;
int n; pl2 arr[10]; bool chk[10];

ll dis(pl2 p1, pl2 p2){
	ll yd = p1.fr-p2.fr, xd = p1.sc-p2.sc;
	return yd*yd + xd*xd;
}

int cnt = 0;
ll ask(pl2 p){
	cnt += 1;
	cout << p.fr << ' ' << p.sc << endl << flush;
	/* ll dst = 1e15;
	for (int i = 1; i <= n; i++){
		if (chk[i]){ continue; }
		dst = min(dst, dis(arr[i], p));
		if (dis(arr[i], p) == 0){ chk[i] = 1; }
	}
	return dst; */
	ll dst; cin >> dst; return dst;
}

ll sq[1000020];

void Main(){
	mt19937 gen(time(NULL));
	uniform_int_distribution<int> rng(0, N);
	for (ll i = 0; i <= N; i++){ sq[i] = i*i; }
	cin >> n;
	// for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int i = 1; i <= n; i++){
		ll y = rng(gen), x = rng(gen);
		vector<pl2> pos;
		ll r = ask({y, x});
		if (r == 0){ continue; }
		int ptr = N;
		for (ll yd = 0; yd <= N; yd++){
			ll ys = yd*yd; ll xs = r - ys;
			while (ptr >= 0){
				if (xs < sq[ptr]){ ptr -= 1; } else{ break; }
			}
			if (sq[ptr] != xs){ continue; }
			ll xd = ptr;
			if (y+yd <= N && x+xd <= N){ pos.push_back({y+yd, x+xd}); }
			if (y+yd <= N && 0 <= x-xd){ pos.push_back({y+yd, x-xd}); }
			if (0 <= y-yd && 0 <= x-xd){ pos.push_back({y-yd, x-xd}); }
			if (0 <= y-yd && x+xd <= N){ pos.push_back({y-yd, x+xd}); }
		}
		unq(pos);
		while (pos.size() > 1){
			//shuffle(all(pos), gen);
			ll r = ask(pos[0]);
			if (r == 0){ break; }
			vector<pl2> tmp;
			for (pl2 p : pos){
				if ( p != pos[0] && dis(pos[0], p) >= r ){ tmp.push_back(p); }
			}
			pos = tmp;
		}
		if (pos.size() == 1){ ask(pos[0]); }
	}
	//cout << "RESULT " << cnt;
}

13. [18204] Dragon Ball II (Diamond V)

만약 드래곤볼이 정확히 7종류였다면, Bitmask를 동반한 Dijkstra로 풀 수 있습니다.

\( D_{v, bit} := \) 현재 위치는 \( v \)번 정점이며, 지금까지 모은 드래곤볼의 상태가 \( bit \)일 때의 최단거리

 

하지만 드래곤볼의 종류가 너무 많습니다. 너무 많은 걸 다루기는 귀찮으니까 그냥 1~7까지 번호를 다시 매기고 탐색하면 안 될까요?

즉, \( f: [1, N] \rightarrow [1, 7] \)인 함수 \( f \)를 만든 뒤, 모든 번호를 \( x \)에서 \( f(x) \)로 바꿔버리고 탐색하면 안 될까요?

 

최단거리로 7종류의 드래곤볼을 모으는 건 (드래곤볼이 7종류 이상이라면) 당연히 존재합니다.

그 7종류의 드래곤볼을 \( a_{1}, a_{2}, \ldots, a_{7} \)이라고 하면, 위 과정에서의 매핑이 랜덤하게 되었다는 가정 하에 7종류의 \( a \)가 모두 다른 드래곤볼 집합에 속해있어야 합니다. 이럴 확률은 \( 7! / 7^7 \approx 0.006 \)입니다.

 

즉 우리는 \( O(2^{7}N \log M) \) 시간에 돌며, 약 99.4% 확률로 틀리는 알고리즘을 만들었습니다.

하지만 이걸 \( f \)를 바꿔가면서 1000번 돌리면 어떻게 될까요?

이제 틀릴 확률은 \( (1 - 7!/7^7)^{1000} \approx 0.002 \), 즉 0.2%가 되었습니다.

대신 시간복잡도가 \( O(1000 \cdot 2^{7} \cdot N \log M) \)이 되었으니, 최적화를 잘 박아줘서 통과해주면 됩니다.

참고로 제 코드는 3444 ms / 4000 ms의 시간동안 돌았습니다.

vector<pi2> adj[1020];
vector<int> bal[1020]; int bit[1020];
int rnd[1020];
const ll INF = 0x3f3f3f3f3f3f3f3f; ll dis[130][1020];
const int ful = 127;

void Main(){
	mt19937 gen(time(NULL)); uniform_int_distribution<int> rng(0, 6);
	int n, m, k; cin >> n >> m >> k;
	while (m--){
		int v, w, dis; cin >> v >> w >> dis;
		adj[v].push_back({w, dis}); adj[w].push_back({v, dis});
	}
	while (k--){
		int v, idx; cin >> v >> idx;
		bal[v].push_back(idx);
	}
	int t = 1000; ll ans = INF;
	while (t--){
		for (int i = 1; i <= n; i++){ bit[i] = 0; rnd[i] = rng(gen); }
		//if (t == 0){ for (int i = 1; i <= n; i++){ cout << rnd[i] << ' '; } cout << endl << flush; }
		for (int i = 1; i <= n; i++){ for (int x : bal[i]){ bit[i] |= 1<<rnd[x]; } }
		memset(dis, 0x3f, sizeof(dis));
		priority_queue< pl3, vector<pl3>, greater<pl3> > pq;
		pq.push({ 0, {bit[1], 1} }); dis[ bit[1] ][1] = 0;
		while (!pq.empty()){
			ll d = pq.top().fr;
			int b = pq.top().sc.fr, v = pq.top().sc.sc;
			if (b == ful){ ans = min(ans, d); break; }
			pq.pop();
			if (dis[b][v] != d){ continue; }
			for (auto [w, dd] : adj[v]){
				int bb = b|bit[w];
				if (dis[bb][w] <= d+dd){ continue; }
				pq.push({ d+dd, {bb, w} }); dis[bb][w] = d+dd;
			}
		}
	}
	if (ans == INF){ cout << -1; } else{ cout << ans; }
}