JOISC18 Highway

문제

oj.uz/problem/view/JOI18_construction

문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz

트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다.

$N<=100000$

 

풀이

Subtask 2

수열의 inversion은 $O(NlogN)$안에 구할 수 있으므로, 각 업데이트별로 요구하는 것들을 naive하게 모두 계산해주면 각 노드별 조상의 수의 합을 시간 복잡도로 갖고, 최악의 경우 $O(N^2logN)$이다.

 

Subtask 3

Subtask 2의 풀이에서 트리를 몇번 그려 보면 같은 수가 여러 번 반복되는 꼴의 수열이 나온다는 것을 알 수 있다. 트리가 일직선 꼴이고, 각 노드에서 리프가 딱 하나씩만 튀어 나와 있는 꼴 등이 최대한 서로 다른 수 구간이 많아지도록 하는 예시일 것 같지만, 실제로 위의 최악의 경우 $O(N^2)$개의 구간을 보도록 하는 반례를 만들기는 매우 어렵다.

inversion을 구하는 연산은 위와 같이 같은 수들이 묶여 있는 꼴이어도 구간의 개수에 비례하도록 풀 수 있기 때문에, 각 업데이트별로 지나는 묶음의 수가 작음을 보이자.

 

Observation 1 : 각 노드에서 같은 수를 묶어 처리한다면, 업데이트별 지나는 묶음의 수의 합은 $O(NlogN)$이다.

업데이트 직후, 각 간선별로 부모와 자식의 색이 다르다면 그 간선을 "separator"이라 부르자.

separator의 수가 곧 묶음의 수이니, 각 업데이트별 지나는 separator의 수의 합이 $O(NlogN)$임을 보이자.

먼저, 트리의 간선을 HLD에서 사용하는 heavy edge와 light edge로 구분하자.

업데이트될 노드에서 루트까지의 경로가 지나는 light edge의 수는 $O(logN)$개 이니, light edge들이 모두 separator이라도 무관하다.

만약 heavy edge가 separator이라면, 그 말은 현재 부모 노드의 간선들 중 separator이 아닌 간선은 하나의 light edge에 해당한다는 것을 알 수 있다. 이는 현재의 업데이트 전에 추가된 노드들 중 부모 노드의 서브트리에 포함되는 가장 마지막으로 등장한 정점은 heavy edge를 제외한 부분의 노드라는 것이다. 또한, 지금 업데이트에서 heavy edge가 separator이라는 것은 지금 업데이트될 정점은 heavy edge의 서브트리이다. 정리하자면, heavy edge가 separator이기 위해서는 무조건 그 전에 한번은 부모 노드의 서브트리 중 heavy edge를 제외한 부분의 업데이트가 가장 마지막으로 등장했어야 함을 의미한다. 이 heavy edge가 separator이 되는 순간을 해당하는 마지막 light edge의 업데이트와 1대1 대응시킬 수 있기 때문에, heavy edge가 separator이 되는 횟수의 최댓값은 light edge 부분의 서브트리의 노드들의 수의 합과 같다.

HLD에서 각 노드들에 대해 heavy edge를 제외한 부분의 서브트리의 노드들의 개수의 합은 최대 $O(NlogN)$이니, 전체 업데이트별 지나는 separator의 수도 $O(NlogN)$과 같다.

 

이제 정점들을 적당히 묶기만 하면 문제를 해결할 수 있다.

루트에서 정점까지의 경로에 대한 체인별로 묶기가 필요하니, 구현에도 HLD를 이용하자.

각 체인별로 묶음의 스택을 하나씩 관리하고, 업데이트가 될때마다, 스택의 뒤쪽에서 몇 개의 구간을 뺀 후 새로운 구간을 삽입하여 업데이트를 관리하고, 빼낸 구간들을 바탕으로 inversion을 계산해준다.

 

스택에 넣고 빠지는 구간의 총 개수가 $O(NlogN)$이고, 각 구간별 inversion을 구해야 하니,  전체 시간복잡도는 $O(Nlog^2N)$이 된다.

 

시간 복잡도 : $O(Nlog^2N)$

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
vector<int> adj[MAXN+10];
int A[MAXN+10], B[MAXN+10];

int par[MAXN+10], sz[MAXN+10];

void dfs(int now)
{
	sz[now]=1;
	for(int nxt : adj[now])
	{
		dfs(nxt);
		sz[now]+=sz[nxt];
	}
}

int head[MAXN+10], dfn[MAXN+10], idfn[MAXN+10], cnt;

void hld(int now)
{
	dfn[now]=++cnt;
	idfn[dfn[now]]=now;

	int heavy=0;
	for(int nxt : adj[now])
	{
		if(sz[heavy]<sz[nxt]) heavy=nxt;
	}
	if(heavy==0) return;

	head[heavy]=head[now];
	hld(heavy);

	for(int nxt : adj[now])
	{
		if(nxt==heavy) continue;
		head[nxt]=nxt;
		hld(nxt);
	}
}

struct Data
{
	int l, r, v;
};
vector<Data> V[MAXN+10];

vector<int> comp;

struct BIT
{
	int tree[MAXN+10];
	void flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=0; }
	void update(int i, int x) { for(; i<=N; i+=(i&-i)) tree[i]+=x; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for(int i=1; i<=N; i++) A[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;

	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		par[v]=u;
		B[i]=v;
	}

	dfs(1);
	head[1]=1;
	hld(1);

	//printf("DFN\n");
	//for(int i=1; i<=N; i++) printf("%d ", dfn[i]); printf("\n");

	V[1].push_back({1, 1, A[1]});
	for(int i=1; i<N; i++)
	{
		int u=par[B[i]], v=B[i];

		int now=v;
		vector<pii> V2;
		while(1)
		{
			vector<pii> VV;
			while(!V[head[now]].empty() && V[head[now]].back().r<=dfn[now])
			{
				VV.push_back({V[head[now]].back().v, V[head[now]].back().r-V[head[now]].back().l+1});
				V[head[now]].pop_back();
			}
			if(!V[head[now]].empty() && V[head[now]].back().l<=dfn[now])
			{
				VV.push_back({V[head[now]].back().v, dfn[now]-V[head[now]].back().l+1});
				V[head[now]].back().l=dfn[now]+1;
			}
			V[head[now]].push_back({dfn[head[now]], dfn[now], A[v]});
			reverse(VV.begin(), VV.end());
			for(auto it : VV) V2.push_back(it);

			if(head[now]==1) break;
			now=par[head[now]];
		}

		reverse(V2.begin(), V2.end());

		ll ans=0;
		//printf("V2 of %d %d is\n", u, v);
		for(auto it : V2)
		{
			//printf("%d %d\n", it.first, it.second);
			ans+=(ll)it.second*(bit.query(N)-bit.query(it.first));
			bit.update(it.first, it.second);
		}
		for(auto it : V2) bit.flush(it.first);
		printf("%lld\n", ans);
	}
}