IOI20 Plants
문제
oj.uz/problem/view/IOI20_plants
문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz
문제 보기 - 식물 비교 (IOI20_plants)
oj.uz
원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다.
이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다.
수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_x<A_y$를 만족하는지, 아니면 $A_x>A_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다.
단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다.
$K<=N<=200000$
$Q<=200000$
풀이
Subtask 1
$K=2$이면, 각 수별로 그 다음 칸의 수와의 대소관계만 알 수 있다.
더 큰 방향으로 방향 간선을 이어주면 하나의 DAG가 완성된다.
쿼리 (x, y)를 해결하기 위해서는 x->y의 경로, y->x의 경로 간선이 존재하는지 확인하기만 하면 되니, 이는 누적합을 통해 해결할 수 있다.
이 서브태스크를 통해 일반적인 상황에서도 직접적으로 정보를 알 수 있는 것은 거리가 K이하인 두 점에 대해서만 알 수 있고, 더 멀리 떨어져 있는 점들의 경우에는 DAG의 간선을 타고 간접적으로 정보를 알아가야 한다는 점을 알 수 있다.
이후 서브태스크들은 수열을 복구하려는 시도에 초점을 맞춘다.
Subtask 2, 3
$N<2K$의 조건이 갖는 의미를 생각해 보자.
어떠한 정점에 대해, 모든 정점들이 이 정점과의 거리가 $K$이하이다. 즉, 이 정점이 볼 수 있는 영역은 이 정점부터 오른쪽으로 $K$개의 수들이고, 거꾸로 이 정점을 볼 수 있는 점들은 이 정점부터 왼쪽으로 $K$개의 수들이니, 결과적으로 이 정점은 모든 정점들의 범위 안에 들어간다.
Observation 1 : 수열 $A$의 최댓값의 위치 $A_i$는 다음 조건을 만족한다.
1. $R_i$는 0이다.
2. $R_i$부터 왼쪽으로 $K-1$개의 칸들은 모두 0이 아니다.
최댓값이니 $R_i=0$은 자명하고, 이 수를 볼 수 있는 왼쪽으로 $K-1$개의 칸들에 대해서는 적어도 그 칸의 수보다 $i$의 수가 더 크니, $R$은 0이 될수 없다.
위 Observation 1과 조건 $N<2K$을 함께 생각하자.
Observation 2 : $N<2K$라면, Observation 1의 조건을 만족하는 최댓값의 후보는 정확히 한 개이다.
만약 위 조건을 만족하는 최댓값의 후보가 2개 이상이라 생각하자.
하나의 0과 왼쪽으로 K-1칸의 0이 아닌 수들을 한 묶음으로 생각하면 최댓값의 후보가 2개 이상이기 위해서는 두 묶음은 겹칠 수 없다. 0이 아닌 수들의 구간에 새로운 0이 위치할 수 없기 때문이다.
즉, 적어도 2K개의 칸이 필요하다는 뜻인데, 이는 $N<2K$ 조건 때문에 모순이다.
또, $R_i$에 대응되는 $A_i$가 적어도 하나 있다고 했으니, 최댓값의 후보가 없을 수는 없고, 정확히 한 개이다.
Observation 3 : $N<2K$라면, 정확히 하나의 $A$가 대응된다.
Observation 2를 통해 전체 수열에서 정확히 하나의 최댓값을 뽑아 낼 수 있다.
이후, 뽑아낸 최댓값을 0으로 만들고 $R$을 그에 맞도록 적당히 조절해주면 귀납적으로 최댓값을 하나씩 뽑아낼 수 있다.
즉, 다른 선택의 여지 없이 정확히 하나의 가능한 후보를 만들어낼 수 있다는 것이다.
Subtask 2를 풀기 위해서는 조건을 만족하는 최댓값 $A_i$를 하나 뽑고, $R_i$를 INF로 만들어준 후, i부터 왼쪽으로 $K-1$개의 수들의 $R$값을 1씩 빼주면 된다.
위 과정은 lazy minimum segment tree를 이용하여 최적화할 수 있다.
최댓값의 조건을 만족하는지 확인하기 위해 단순 $R_i$의 최솟값을 관리하는 segment tree 하나와, $R_i=0$으로 인해 최댓값의 후보가 되지 못하는 오른쪽 $K$개의 칸들에 +1을 한 segment tree하나를 더 이용하여, 두번째 segment tree에서 0이 되는 위치를 확인하고, 이를 이용하여 각 segment tree에 왼쪽 구간에 -1을 해준 후, 새로 0이 된 구간으로 인해 최댓값의 후보가 되지 못하는 위치들에 다시 업데이트를 해주면 된다.
Subtask 2, 3의 풀이가 꽤 복잡하기 때문에, 전체 정해의 풀이도 이 틀에서 크게 벗어나지 않을 것이라 예측할 수 있다.
Subtask 5
이제 $N<2K$를 만족하지 않는다 하면, 각 상황에서 최댓값의 후보가 정확히 정해지지 않을 수 있고, 이로 인해 가능한 $A$가 하나로 정해지지 않을 수 있다.
위 Subtask 1에서의 거리가 K 이상인 두 점에 대해서는 정확한 정보를 알 수 없고, 오직 거리가 K이하인 점들에 대해서만 알 수 있다는 점을 생각해보자.
Observation 4 : Subtask 2, 3의 알고리즘을 통해 얻을 수 있는 어떤 $A$에 대해서도 거리가 K 이하인 점들에 대해서는 대소관계가 같다(하나로 정해진다).
Exchange Arguments를 이용하자. 만약 최댓값을 뽑는 타임라인을 기준으로 인접한 두 칸의 거리가 K 이상이라면 아무런 제약 조건 없이 뒤바꿀 수 있으니, 인접한 두 칸의 거리가 K이하일 때만 생각하자.
두 점 $i, j$가 거리가 $K$ 이하이고, $j$가 $i$의 오른쪽이라고 가정하자. 이제, $i$가 $j$보다 먼저 뽑히는 상황과 $j$가 $i$보다 먼저 뽑히는 상황이 동시에 존재할 수 없다는 것을 증명하면 된다.
$i$가 $j$보다 먼저 뽑히는 $A$가 존재한다면, $R_i$가 0이니, 이에 의해 $R_i$가 제거되기 전까지 $R_j$는 최댓값의 후보가 될수 없다. 즉 $j$는 절대 $i$보다 먼저 뽑힐 수 없다.
$j$가 $i$보다 먼저 뽑히는 $A$가 존재한다면, $R_j$가 0이고, $R_i$는 0이 아니니, $R_i$가 0이 되기 위해서는 $R_j$가 먼저 제거되는 것이 필수적이다. 즉, $i$는 절대 $j$보다 먼저 뽑힐 수 없다.
위 Observation 4이 의미하는 것은, 거리가 K 이상인 점 쌍들에 대해서는 직접적인 대소관계를 비교할 수 없고, 거리가 K이하인 점 쌍들에 대해서는 모든 쌍에 대해 직접적인 대소관계가 정확히 하나로 정해지며, 그를 구하는 방법은 가능한 임의의 A를 구한 후 이 A의 대소관계를 이용하는 것이다. 간접적으로 비교 가능한 점들은 직접적으로 비교 가능한 점들을 이용하여 모든 쌍에 대해 DAG를 만들고 DAG 위에서 경로가 존재하는지 판별하는 것으로 해결할 수 있다.
전체 알고리즘은 $O(NlogN)$에 가능한 임의의 A를 복구하고, $O(NK)$에 DAG를 만든 후, $O(N^3)$에 floyd-warshall 을 통하여 모든 경로 쌍에 대해 도달 가능성의 답을 구하면 된다.
Subtask 7
이제 남은 것은 위 알고리즘을 최적화하는 것 뿐이다.
하나의 A를 찾는 것은 이미 lazy segment tree를 이용하여 $O(NlogN)$으로 최적화하였으니, DAG를 만드는데 걸리는 시간 $O(NK)$와 도달성을 판별하는데 걸리는 시간 $O(N^3)$만 최적화하면 된다.
위 $O(NK)$에 완전한 DAG를 만드는 과정은 다음과 같이 요약할 수 있다.
각 점별로 자기보다 큰 정점들 중 $[i-k+1, i+K-1]$, 즉 직접 연결될 가능성에 있는 범위에 속하는 정점들에 대하여 모두 간선을 이어준다.
Observation 5 : 각 점별로 자기보다 큰 정점들 중 $[i-k+1, i+K-1]$에 속하는 정점들에 대하여 모두 간선을 이어주는 대신, 자기보다 큰 정점들 중 $[i-K+1, i]$중 최소 원소, $[i, i+K-1]$중 최소 원소와만 간선을 이어주어도 같은 도달 가능성을 갖는다.
귀납법을 이용하여, v이상의 모든 칸에 대해서는 위 명제가 성립한다 가정하자. 이제 v에 도달 가능하고 작은 원소인 u에서 범위 중 최소 원소가 아닌 w에 도달 가능할 때 u->v, v->w경로가 모두 존재해 u->w 경로도 존재함을 보이면 된다. v->w는 귀납 가정에 의해 성립하고, u->v는 위 관찰의 간선 중 하나이니, 성립한다.
위 과정에서 왼쪽으로의 간선을 $L[u]$, 오른쪽으로의 간선을 $R[u]$이라 하자.
간선의 개수는 $O(N)$개로 줄였으니, 이제 쿼리를 처리하는 과정만 줄이면 된다.
Observation 6 : Observation 5로 만든 그래프는 $(i, A_i)$를 플로팅한 점들에 대한 Planar Graph이다.
경우를 나누어 모든 경우에 대해 따져 보면, 만약 어떤 두 간선이 겹친다고 가정하면, Observation 5의 조건을 절대 만족할 수 없다는 것을 알 수 있다.
Planar Graph이고, DAG이니, 도달 가능성을 구간에 대한 문제로 바꾸어 생각해 보려는 전략을 세울 수 있다. 이를 통해 Sparse Table 을 이용한 풀이를 유도할 수 있다.
Observation 7 : $A_u<A_v$일 때 u->v 경로가 존재하기 위한 필요충분조건은 u에서 L[u]만을 타고 v의 위치까지 따라간 높이보다 $A_v$가 높거나, u에서 R[u]만을 타고 v의 위치까지 따라간 높이보다 $A_v$가 높은 것이다.
원래 그래프를 Observation 5를 이용하여 압축한 논리와 그 과정을 생각해보면, u에서 시작해서 도달 가능한 정점들의 집합은 L[u]를 따라가면서 얻는 계단 모양과 R[u]를 따라가면서 얻는 계단 모양의 위쪽 부분이라는 것을 알 수 있다.
위 따라가는 과정을 그대로 할 수는 없으니, 이에 대한 sparse table을 만들고, sparse table 위에서의 탐색을 해주면 된다.
전체 시간복잡도는 하나의 해 탐색에 $O(NlogN)$, 그래프 구성에 $O(NlogN)$, 스파스 테이블 구성에 $O(NlogN)$, 쿼리당 스파스 테이블 탐색이 $O(QlogN)$으로, 전체 시간 복잡도 $O((N+Q)logN)$이다.
시간 복잡도 : $O((N+Q)logN)$
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int INF = 1e8;
int N, K, R[MAXN+10], H[MAXN+10];
struct SEG
{
pii tree[MAXN*4+10];
int lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
tree[node].first+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]={0, tl};
lazy[node]=0;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
void update(int node, int tl, int tr, int l, int r, int k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
void update2(int node, int tl, int tr, int p, int k)
{
busy(node, tl, tr);
if(tl==tr)
{
tree[node].first=k;
return;
}
int mid=tl+tr>>1;
if(p<=mid) update2(node*2, tl, mid, p, k);
else update2(node*2+1, mid+1, tr, p, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
pii query(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return {INF, -1};
int mid=tl+tr>>1;
return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
void query2(int node, int tl, int tr, int l, int r, vector<int> &V)
{
busy(node, tl, tr);
if(tree[node].first!=0) return;
if(r<tl || tr<l) return;
if(tl==tr)
{
V.push_back(tl);
return;
}
int mid=tl+tr>>1;
query2(node*2, tl, mid, l, r, V);
query2(node*2+1, mid+1, tr, l, r, V);
}
void init()
{
init(1, 0, N-1);
}
void update(int l, int r, int k)
{
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) update(1, 0, N-1, l, r, k);
else
{
update(1, 0, N-1, l, N-1, k);
update(1, 0, N-1, 0, r, k);
}
}
void update2(int p, int k)
{
p=(p%N+N)%N;
update2(1, 0, N-1, p, k);
}
pii query(int l, int r)
{
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) return query(1, 0, N-1, l, r);
else return min(query(1, 0, N-1, l, N-1), query(1, 0, N-1, 0, r));
}
vector<int> query2(int l, int r)
{
vector<int> ret;
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) query2(1, 0, N-1, l, r, ret);
else
{
query2(1, 0, N-1, l, N-1, ret);
query2(1, 0, N-1, 0, r, ret);
}
return ret;
}
}seg1, seg2, seg3;
int LL[MAXN*2+10][30], RR[MAXN*2+10][30];
void init(int _K, vector<int> _R)
{
K=_K; N=_R.size();
for(int i=0; i<N; i++) R[i]=_R[i];
seg1.init(); seg2.init(); seg3.init();
for(int i=0; i<N; i++)
{
seg1.update2(i, R[i]);
seg2.update2(i, R[i]);
}
for(int i=0; i<N; i++) if(R[i]==0) seg1.update(i+1, i+K-1, 1);
for(int i=N-1; i>=0; i--)
{
vector<int> V;
assert(seg1.tree[1].first+seg1.lazy[1]==0);
int now=seg1.tree[1].second; H[now]=i;
assert(seg2.query(now-K+1, now-1).first>=1);
seg1.update(now+1, now+K-1, -1);
seg1.update2(now, INF);
seg2.update2(now, INF);
seg2.update(now-K+1, now-1, -1);
seg1.update(now-K+1, now-1, -1);
V=seg2.query2(now-K+1, now-1);
for(auto it : V) seg1.update(it+1, it+K-1, 1);
}
//for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
vector<pii> V;
for(int i=0; i<N; i++) V.push_back({H[i], i});
sort(V.begin(), V.end(), greater<pii>());
for(int i=0; i<N; i++) seg3.update2(i, INF);
memset(LL, -1, sizeof(LL));
memset(RR, -1, sizeof(RR));
for(int i=0; i<V.size(); i++)
{
int now=V[i].second;
pii t1=seg3.query(now-K+1, now), t2=seg3.query(now, now+K-1);
if(t1.first!=INF)
{
int p=t1.second;
if(p<now)
{
LL[now][0]=p;
LL[now+N][0]=p+N;
}
else
{
LL[now+N][0]=p;
}
}
if(t2.first!=INF)
{
int p=t2.second;
if(now<p)
{
RR[now][0]=p;
RR[now+N][0]=p+N;
}
else
{
RR[now][0]=p+N;
}
}
seg3.update2(now, H[now]);
}
for(int i=1; i<=20; i++)
{
for(int j=0; j<N+N; j++)
{
if(LL[j][i-1]!=-1) LL[j][i]=LL[LL[j][i-1]][i-1];
if(RR[j][i-1]!=-1) RR[j][i]=RR[RR[j][i-1]][i-1];
}
}
return;
}
int compare_plants(int x, int y)
{
int ans=0;
if(x<y)
{
if(H[x]<H[y])
{
int now=x+N;
for(int i=20; i>=0; i--) if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
if(now+K-1>=y+N && H[now%N]<=H[y]) return -1;
now=x+N;
for(int i=20; i>=0; i--) if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
if(now-K+1<=y && H[now%N]<=H[y]) return -1;
}
else
{
int now=y;
for(int i=20; i>=0; i--) if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
if(now+K-1>=x+N && H[now%N]<=H[x]) return 1;
now=y;
for(int i=20; i>=0; i--) if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
if(now-K+1<=x && H[now%N]<=H[x]) return 1;
}
}
else
{
if(H[x]<H[y])
{
int now=x;
for(int i=20; i>=0; i--) if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
if(now+K-1>=y+N && H[now%N]<=H[y]) return -1;
now=x;
for(int i=20; i>=0; i--) if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
if(now-K+1<=y && H[now%N]<=H[y]) return -1;
}
else
{
int now=y+N;
for(int i=20; i>=0; i--) if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
if(now+K-1>=x+N && H[now%N]<=H[x]) return 1;
now=y+N;
for(int i=20; i>=0; i--) if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
if(now-K+1<=x && H[now%N]<=H[x]) return 1;
}
}
return 0;
}