<div id="readability-page-1" class="page"><div>문제 및 채점: <a href="https://oj.uz/problem/view/IOI20_plants" target="_blank" rel="noopener">oj.uz</a>

서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다.

풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시로 들어 설명하겠다.

<figure data-origin-width="559" data-origin-height="66" data-filename="plants_1.png" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/bo0P81/btqJnFZoc9i/pnE5KAFOqWFicAykDlGmgK/img.png" data-origin-width="559" data-origin-height="66" data-filename="plants_1.png" data-ke-mobilestyle="widthContent"></figure>
이 때, 최대 크기를 가질 수 있는 식물을 찾을 건데, $i$ 번 식물이 아래 두 조건을 만족하면 최대 크기를 가질 수 있다:
　1) $R[i] = 0$: 시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$ 번 식물보다 큰 식물이 없음
　2) $R[j] = 0$ ($j$는 $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 식물 번호): 반시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$번 식물보다 큰 식물이 없음

$2K &gt; N$인 경우(서브태스크 2, 3), 위 조건을 만족하는 $i$는 유일하며 전체 중 가장 큰 크기를 가지는 식물이다.

예시에서 두 조건을 만족하는 $i$는 5로 유일하다. 예를 들어, 6의 경우 $R[6] = 0$으로 1)번 조건을 만족하지만, $R[5] = 0$이기 때문에 2)번 조건을 만족하지 못한다.

만약 조건을 만족하는 $i$가 여러 개인 경우 그중 아무거나 하나를 찾고, $i$번 식물의 크기가 가장 크다고 가정한다. 그리고 $R[i]$의 값을 없애고, $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 $R$ 배열 값을 1 감소시킨다.

<figure data-filename="plants_2.png" data-origin-width="559" data-origin-height="98" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/cZsGnP/btqJpiiloIt/5CyvKlXHmls4ZwLTUnH350/img.png" data-filename="plants_2.png" data-origin-width="559" data-origin-height="98" data-ke-mobilestyle="widthContent"></figure>
그러면 $R[3]$의 값이 1 감소하여 0이 되었고, $R[4]$의 값이 1 감소하여 1이 되었다. 그리고 위의 과정을 반복한다.

<figure data-filename="plants_3.png" data-origin-width="560" data-origin-height="212" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/DAaQL/btqJls0lMZR/NklqX84AoScPTXGmWnf0xk/img.png" data-filename="plants_3.png" data-origin-width="560" data-origin-height="212" data-ke-mobilestyle="widthContent"></figure>
지금 상황에서 두 조건을 만족하는 $i$는 3과 7로 유일하지 않다. 즉, 3번 식물과 7번 식물의 크기 비교가 불가능한 상황임을 알 수 있다. 앞서 말했던 것처럼, $i$가 여러 개인 경우 그중 아무거나 하나를 찾자. 편의상 번호가 제일 작은 3번 식물로 과정을 진행하겠다.

<figure data-filename="plants_4.png" data-origin-width="560" data-origin-height="478" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/bNY8RF/btqJjuYsQoo/VLhWG5CHTYeSKTPuTgjxR1/img.png" data-filename="plants_4.png" data-origin-width="560" data-origin-height="478" data-ke-mobilestyle="widthContent"></figure>
이 방법으로 가능한 여러 식물들의 크기 구성 중 하나를 배열 $H$에 기록했다.

서브태스크 2 (14 점)
$N \leq 5000, 2K &gt; N$. 위의 방법을 naive하게 구현하면 시간복잡도는 $O(NK)$가 되며, $2K &gt; N$을 만족하는 경우 매 순간 최대 크기를 가지는 식물 후보 $i$가 유일하므로, 가능한 식물 크기 구성이 유일하다. 따라서 구한 배열 $H$로 모든 질문을 해결할 수 있다.

서브태스크 3, 4 (13, 17 점)
위의 방법을 lazy propagation을 이용한 segment tree와, 집합에서 lower bound와 left, right iteration이 가능한 set 같은 자료구조를 사용하면 $O(N \lg N)$ 시간에 해결할 수 있다. 배열 $H$의 내용만 가지고는 크기를 비교할 수 없는 식물 쌍을 확인할 수 없다. 서브태스크 3, 4는 식물 크기를 비교할 수 없는 쌍에 대한 고려를 하지 않아도 해결할 수 있다.

다음 서브태스크들을 풀기 위해 필요한 관찰
식물 $i$에 대해 시계방향과 반시계방향으로 $K-1$ 이내에 있는 식물들은 배열 $H$에 있는 값의 대소 비교를 통해 식물 크기를 비교할 수 있다.

서브태스크 5 (11 점)
$N \leq 300$. 위의 사실을 이용하여, $a$ 번 식물과 $b$ 번 식물의 크기 비교를 할 수 있고, $a$ 번 식물의 크기가 $b$번 식물보다 큰 경우 정점 $a$에서 정점 $b$로 가는 방향성 간선을 만들어, 간선의 개수가 $O(NK)$가 되는 DAG(Directed Acyclic Graph)를 만들 수 있다. Bellman-Ford 알고리즘을 사용하여 모든 쌍 $(i, j)$에 대해 DAG에서 경로가 있는지 미리 계산할 수 있다. DAG에서 $i$에서 $j$로 가는 경로가 있으면 $i$ 번 식물의 크기가 $j$ 번 식물의 크기보다 큰 것이고, 반대로 $j$에서 $i$로 가는 경로가 있으면 $j$ 번 식물의 크기가 $i$ 번 식물의 크기보다 큰 것이다. 둘다 경로가 없으면 두 식물의 크기를 비교할 수 없음을 의미한다.

다음 서브태스크들을 풀기 위해 필요한 관찰
<figure data-filename="plants_5.png" data-origin-width="861" data-origin-height="98" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/0lphT/btqJjvXk49d/v0pCQWXIzcZMUXiffBntAk/img.png" data-filename="plants_5.png" data-origin-width="861" data-origin-height="98" data-ke-mobilestyle="widthContent"></figure>
위는 설명을 위한 다른 예시다. $K = 3$이며, $R[i]$에 적힌 값들은 처음 들어온 배열 $R$의 값이고, $H[i]$에 적힌 값들은 앞에 설명한 방법으로 구한 배열 $H$의 값이다.

이 예시에서 3번 식물과 9번 식물의 크기를 비교할 수 있는데, 왜냐하면 3번 식물의 크기는 5번 식물의 크기보다 크고, 5번 식물의 크기는 7번 식물의 크기보다 크고, 7번 식물의 크기는 9번 식물의 크기보다 크기 때문이다. 반면, 3번 식물과 10번 식물은 크기 비교를 할 수 없다.

3번 식물을 기준으로 오른쪽(원형에서는 시계방향)으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 5번 식물이 나온다. 5번 식물을 기준으로 오른쪽으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 7번 식물이 나온다. 이때, 7번 식물은 자명히 3번 식물보다 크기가 작으며, 7번 식물은 9번 식물과 충분히 거리가 인접하므로 크기 비교를 할 수 있고, 9번 식물은 7번 식물보다 크기가 작다. 이처럼 모든 식물에 대해 오른쪽 방향으로 자기와 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾는다. 마찬가지로 왼쪽 방향에 대해서도 진행한다. 이 과정은 set을 이용하여 $O(N \lg N)$에 구현할 수 있다.

서브태스크 6 (15 점)
항상 1번 식물과 다른 식물 $j$를 비교하는 질문만 들어오는 서브태스크다. 1번 식물에 대해 오른쪽으로 갈 때 나타나는 식물들의 순서와, 왼쪽으로 갈 때 나타나는 식물들의 순서를 미리 구한다. 주어지는 $j$에 대해 $j$보다 왼쪽에 있으면서 1번 식물에서 오른쪽으로 갈 때 나타나는 식물들 중 가장 $j$와 가까운 식물의 번호를 이분탐색으로 구한다. 그리고 그 식물과 $j$번 식물의 크기를 비교하여 $j$번 식물의 크기가 더 작다면 1번 식물의 크기가 더 크다는 뜻이다. 마찬가지의 확인을 왼쪽 방향에 대해서도 해준다. 이는 주어지는 질문을 $O(\lg N)$에 해결한다.

서브태스크 7 (25 점)
마지막 서브태스크다. 서브태스크 6에서 1번 식물에 대해 한 방향에 대해 나타나는 식물 순서를 미리 구하고 이분탐색한 과정을 sparse table을 이용해 공간복잡도 $O(N \lg N)$에 질문마다 시간복잡도 $O(\lg N)$에 해결할 수 있다.

</div></div>

PS 이야기

문제 및 채점: oj.uz
 
서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다.
 
풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시로 들어 설명하겠다.
 
이 때, 최대 크기를 가질 수 있는 식물을 찾을 건데, $i$ 번 식물이 아래 두 조건을 만족하면 최대 크기를 가질 수 있다:
　1) $R[i] = 0$: 시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$ 번 식물보다 큰 식물이 없음
　2) $R[j] = 0$ ($j$는 $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 식물 번호): 반시계방향으로 연속한 $K-1$ 개의 식물 중에 $i$번 식물보다 큰 식물이 없음
 
$2K > N$인 경우(서브태스크 2, 3), 위 조건을 만족하는 $i$는 유일하며 전체 중 가장 큰 크기를 가지는 식물이다.
 
예시에서 두 조건을 만족하는 $i$는 5로 유일하다. 예를 들어, 6의 경우 $R[6] = 0$으로 1)번 조건을 만족하지만, $R[5] = 0$이기 때문에 2)번 조건을 만족하지 못한다.
 
만약 조건을 만족하는 $i$가 여러 개인 경우 그중 아무거나 하나를 찾고, $i$번 식물의 크기가 가장 크다고 가정한다. 그리고 $R[i]$의 값을 없애고, $i$를 기준으로 반시계방향으로 연속한 $K-1$ 개의 $R$ 배열 값을 1 감소시킨다.
 
그러면 $R[3]$의 값이 1 감소하여 0이 되었고, $R[4]$의 값이 1 감소하여 1이 되었다. 그리고 위의 과정을 반복한다.
 
지금 상황에서 두 조건을 만족하는 $i$는 3과 7로 유일하지 않다. 즉, 3번 식물과 7번 식물의 크기 비교가 불가능한 상황임을 알 수 있다. 앞서 말했던 것처럼, $i$가 여러 개인 경우 그중 아무거나 하나를 찾자. 편의상 번호가 제일 작은 3번 식물로 과정을 진행하겠다.
 
이 방법으로 가능한 여러 식물들의 크기 구성 중 하나를 배열 $H$에 기록했다.
 
서브태스크 2 (14 점)
$N \leq 5000, 2K > N$. 위의 방법을 naive하게 구현하면 시간복잡도는 $O(NK)$가 되며, $2K > N$을 만족하는 경우 매 순간 최대 크기를 가지는 식물 후보 $i$가 유일하므로, 가능한 식물 크기 구성이 유일하다. 따라서 구한 배열 $H$로 모든 질문을 해결할 수 있다.
 
서브태스크 3, 4 (13, 17 점)
위의 방법을 lazy propagation을 이용한 segment tree와, 집합에서 lower bound와 left, right iteration이 가능한 set 같은 자료구조를 사용하면 $O(N \lg N)$ 시간에 해결할 수 있다. 배열 $H$의 내용만 가지고는 크기를 비교할 수 없는 식물 쌍을 확인할 수 없다. 서브태스크 3, 4는 식물 크기를 비교할 수 없는 쌍에 대한 고려를 하지 않아도 해결할 수 있다.
 
다음 서브태스크들을 풀기 위해 필요한 관찰
식물 $i$에 대해 시계방향과 반시계방향으로 $K-1$ 이내에 있는 식물들은 배열 $H$에 있는 값의 대소 비교를 통해 식물 크기를 비교할 수 있다.
 
서브태스크 5 (11 점)
$N \leq 300$. 위의 사실을 이용하여, $a$ 번 식물과 $b$ 번 식물의 크기 비교를 할 수 있고, $a$ 번 식물의 크기가 $b$번 식물보다 큰 경우 정점 $a$에서 정점 $b$로 가는 방향성 간선을 만들어, 간선의 개수가 $O(NK)$가 되는 DAG(Directed Acyclic Graph)를 만들 수 있다. Bellman-Ford 알고리즘을 사용하여 모든 쌍 $(i, j)$에 대해 DAG에서 경로가 있는지 미리 계산할 수 있다. DAG에서 $i$에서 $j$로 가는 경로가 있으면 $i$ 번 식물의 크기가 $j$ 번 식물의 크기보다 큰 것이고, 반대로 $j$에서 $i$로 가는 경로가 있으면 $j$ 번 식물의 크기가 $i$ 번 식물의 크기보다 큰 것이다. 둘다 경로가 없으면 두 식물의 크기를 비교할 수 없음을 의미한다.
 
다음 서브태스크들을 풀기 위해 필요한 관찰
위는 설명을 위한 다른 예시다. $K = 3$이며, $R[i]$에 적힌 값들은 처음 들어온 배열 $R$의 값이고, $H[i]$에 적힌 값들은 앞에 설명한 방법으로 구한 배열 $H$의 값이다.
 
이 예시에서 3번 식물과 9번 식물의 크기를 비교할 수 있는데, 왜냐하면 3번 식물의 크기는 5번 식물의 크기보다 크고, 5번 식물의 크기는 7번 식물의 크기보다 크고, 7번 식물의 크기는 9번 식물의 크기보다 크기 때문이다. 반면, 3번 식물과 10번 식물은 크기 비교를 할 수 없다.
 
3번 식물을 기준으로 오른쪽(원형에서는 시계방향)으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 5번 식물이 나온다. 5번 식물을 기준으로 오른쪽으로 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾으면 7번 식물이 나온다. 이때, 7번 식물은 자명히 3번 식물보다 크기가 작으며, 7번 식물은 9번 식물과 충분히 거리가 인접하므로 크기 비교를 할 수 있고, 9번 식물은 7번 식물보다 크기가 작다. 이처럼 모든 식물에 대해 오른쪽 방향으로 자기와 크기 비교가 가능하며 자기보다 크기가 작으면서 제일 크기가 큰 식물을 찾는다. 마찬가지로 왼쪽 방향에 대해서도 진행한다. 이 과정은 set을 이용하여 $O(N \lg N)$에 구현할 수 있다.
 
서브태스크 6 (15 점)
항상 1번 식물과 다른 식물 $j$를 비교하는 질문만 들어오는 서브태스크다. 1번 식물에 대해 오른쪽으로 갈 때 나타나는 식물들의 순서와, 왼쪽으로 갈 때 나타나는 식물들의 순서를 미리 구한다. 주어지는 $j$에 대해 $j$보다 왼쪽에 있으면서 1번 식물에서 오른쪽으로 갈 때 나타나는 식물들 중 가장 $j$와 가까운 식물의 번호를 이분탐색으로 구한다. 그리고 그 식물과 $j$번 식물의 크기를 비교하여 $j$번 식물의 크기가 더 작다면 1번 식물의 크기가 더 크다는 뜻이다. 마찬가지의 확인을 왼쪽 방향에 대해서도 해준다. 이는 주어지는 질문을 $O(\lg N)$에 해결한다.
 
서브태스크 7 (25 점)
마지막 서브태스크다. 서브태스크 6에서 1번 식물에 대해 한 방향에 대해 나타나는 식물 순서를 미리 구하고 이분탐색한 과정을 sparse table을 이용해 공간복잡도 $O(N \lg N)$에 질문마다 시간복잡도 $O(\lg N)$에 해결할 수 있다.
 
더보기
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
typedef pair<int, int> pii;
int N, K, R[MAXN];
int H[MAXN], nxt_r[MAXN][18], nxt_l[MAXN][18];
template <typename T>
struct SegTree{
	int n_bits, TS, ST;
	int range_l(int x){ return ((x<<(__builtin_clz(x)-31+n_bits)) ^ (1<<n_bits)) + 1; }
	int range_r(int x){ return ((x<<(__builtin_clz(x)-31+n_bits) ^ ((1<<(__builtin_clz(x)-31+n_bits))-1)) ^ (1<<n_bits)) + 1; }
	struct Value{
		T value, lazysum;
	};
	vector<Value> tree;
	SegTree(int arr[]){
		n_bits = 32-__builtin_clz(N-1);
		TS = 1 << n_bits+1; ST = TS/2-1;
		tree.resize(TS, {0, 0});
		for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9;
		for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
	}
	void propagate(int n){
		if (n <= ST){
			tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
			tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
		}
		tree[n].lazysum = 0;
	}
	void update(int n, int l, int r, const int &v){
		int s = range_l(n), e = range_r(n);
		if (l > r || e < l || r < s) return;
		if (l <= s && e <= r){
			tree[n].value += v, tree[n].lazysum += v;
			return;
		}
		propagate(n);
		update(n*2, l, r, v);
		update(n*2+1, l, r, v);
		tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
	}
	int findzero(int n){
		if (tree[n].value != 0) return 0;
		propagate(n);
		if (n > ST) return n-ST;
		if (!tree[n*2].value) return findzero(n*2);
		else if (!tree[n*2+1].value) return findzero(n*2+1);
		else assert(0);
	}
};
struct ZeroContainer{
	set<int> pos, non_covered;
	set<int>::iterator _left(set<int>::iterator it){
		auto ret = it;
		if (ret == pos.begin()) ret = pos.end();
		return --ret;
	}
	set<int>::iterator _right(set<int>::iterator it){
		auto ret = it; ret++;
		if (ret == pos.end()) return pos.begin();
		return ret;
	}
	void insert(int p){
		auto it = pos.insert(p).first;
		auto l = _left(it), r = _right(it);
		if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p);
		if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r);
	}
	void remove(int p){
		auto it = pos.find(p);
		auto l = _left(it), r = _right(it);
		if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r);
		pos.erase(it);
	}
	int pop_smallest(){
		int ret = *non_covered.begin(); non_covered.erase(ret);
		remove(ret);
		return ret;
	}
};
int go_left(int n, int d)
{ return (n - d%N - 1 + N)%N + 1; }
int go_right(int n, int d)
{ return (n + d%N - 1 + N)%N + 1; }
void init(int K, vector<int> r)
{
	::K = K;
	N = r.size();
	for (int i=1;i<=N;i++) R[i] = r[i-1];
	{
		SegTree<int> segtree(R);
		ZeroContainer zc;
		for (int ord=N;ord;ord--){
			for (;;){
				int p = segtree.findzero(1);
				if (!p) break;
				zc.insert(p);
				segtree.update(1, p, p, 1e9);
			}
			int x = zc.pop_smallest();
			H[x] = ord;
			segtree.update(1, max(1, x-K+1), x-1, -1);
			if (x-K+1 < 1) segtree.update(1, N-(1-(x-K+1))+1, N, -1);
		}
	}
	{
		set <pii> s;
		for (int i=1;i<=K;i++) s.insert({H[i], i});
		for (int i=1;i<=N;i++){
			auto it = s.lower_bound({H[i], 0});
			if (it != s.begin()){
				it--;
				nxt_r[i][0] = (it->second - i + N) % N;
			}
			int t = (i+K-1)%N+1;
			s.insert({H[t], t});
			s.erase({H[i], i});
		}
	}
	{
		set <pii> s;
		for (int i=1;i<K;i++) s.insert({H[i], i});
		for (int i=1;i<=N;i++){
			int t = (i+K-2)%N+1;
			auto it = s.lower_bound({H[t], 0});
			if (it != s.begin()){
				it--;
				nxt_l[t][0] = (t - it->second + N) % N;
			}
			s.insert({H[t], t});
			s.erase({H[i], i});
		}
	}
	for (int i=0;i+1<18;i++) for (int j=1;j<=N;j++){
		nxt_l[j][i+1] = min(N+10, nxt_l[go_left(j, nxt_l[j][i])][i] + nxt_l[j][i]);
		nxt_r[j][i+1] = min(N+10, nxt_r[go_right(j, nxt_r[j][i])][i] + nxt_r[j][i]);
	}
}
bool has_left_path(int a, int b)
{
	int d = (a-b+N)%N;
	for (int i=18;i--;) if (d >= nxt_l[a][i]){
		d -= nxt_l[a][i];
		a = go_left(a, nxt_l[a][i]);
	}
	return (a-b+N)%N < K && H[a] >= H[b];
}
bool has_right_path(int a, int b)
{
	int d = (b-a+N)%N;
	for (int i=18;i--;) if (d >= nxt_r[a][i]){
		d -= nxt_r[a][i];
		a = go_right(a, nxt_r[a][i]);
	}
	return (b-a+N)%N < K && H[a] >= H[b];
}
int compare_plants(int a, int b)
{
	a++; b++;
	if (has_left_path(a, b) || has_right_path(a, b)) return 1;
	if (has_left_path(b, a) || has_right_path(b, a)) return -1;
	return 0;
}

IOI2020 Day1 plants 풀이

댓글