[codeforces] 1150E. Tree Generator™

문제

https://codeforces.com/contest/1150/problem/E

Problem - E - Codeforces

 

풀이

우선 괄호열과 트리 간의 어떤 관계가 있는지를 관찰해보자.

s=(()(()))이라고 하면, 트리는 다음과 같이 그려진다.

트리를 주의깊게 살펴보면 depth가 늘어날때 여는 괄호이고, depth가 줄어들때 닫는 괄호이다.

즉, 여는 괄호가 나오면 새로 자식노드를 만들고, 닫는괄호가 나오면 퇴각하면 되는 것이다.

따라서, 지금까지의 괄호열의 prefix에서 (여는 괄호의 개수)-(닫는 괄호의 개수)가 tree에서의 depth가 되는 것이다.

 

여기서 구하고자 하는 tree의 지름은 두 노드 사이의 거리의 최대값이 된다.

두 노드 사이의 거리는 다음과 같이 표현할 수 있다.

$$d(u,v)=depth(u)+depth(v)-2depth(lca(u,v))$$

 

여기서 $lca(u,v)$는 두 노드의 lowest common ancestor이다.

괄호열이 트리를 순서대로 순회하고 있으므로, $lca(u,v)$는 u와 v사이의 depth값중 가장 작은 값을 가지는 점이 된다.

따라서 문제에서 구해야 할 것은 다음과 같다.

$$\max(depth(u)+depth(v)-2depth(k))(u \leq k \leq v)$$

 

이것을 단순히 계산하면 depth를 미리 계산해 놓는다 하여도,  쿼리마다 $O(n^3)$의 시간복잡도가 필요하다.

이를 쿼리마다 빠르게 계산하기 위해서, segment tree를 사용한다.

 

segment tree의 각 노드에서 관리하는 값을 하위 구간의 $diam=\max(depth(u)+depth(v)-2depth(k))(u \leq k \leq v)$라 하자.

그러면 다음과 같은 경우로 나눌 수 있다.

 

case 1) u,k,v가 전부 왼쪽 자식에 있을 경우

이 경우는 왼쪽 자식의 $diam$이 정답이 된다.

 

case 2) u,k는 왼쪽자식, v는 오른쪽 자식에 있을 경우

이 경우에는 왼쪽에서의 $\max(depth(u)-2depth(k))$ 와 오른쪽의 $\max(depth(v))$의 합이 답이 된다.

단, 여기서 주의해야 할것은, 현재 오른쪽 자식에 있는 $depth(v)$는 현재 왼쪽자식의 정보없이 구한 값이다.

따라서, $\max(depth(v))$에 현재의 depth를 더해주어야 한다.

 

case 3) u는 왼쪽자식, k,v는 오른쪽 자식에 있을 경우

이 경우는 왼쪽의 $\max(depth(u))$와 오른쪽의 $\max(depth(v)-2depth(k))$의 합이 답이 된다.

case 2와 비슷하게, 오른쪽 자식의 $depth(v)$는 현재 왼쪽자식의 정보없이 구한 값이다.

따라서 각각의 depth에 현재의 depth를 더해주어야 하므로, $\max(depth(v)-2depth(k))$에 현재 depth를 빼준다.

 

case 4) u,k,v 모두 오른쪽 자식에 있을 경우

이 경우 오른쪽 자식의 $diam$이 정답이 된다.

depth의 변동이 있지만 모두 더하면 0이므로 그냥 값을 그대로 사용한다.

 

이 4가지 case중 최대값이 구하고자 하는 $diam$의 값이 된다. 

여기서 추가적으로 $\max(depth(v)-2depth(k))$와 $\max(depth(u)-2depth(k))$도 구해야 함을 알 수 있다.

 

위의 방법과 똑같은 방법으로 각각을 구할 수 있다.

각각 3가지의 case가 나오고, 코드가 아래에 있으니 과정은 생략하겠다.

-가 붙은 부분의 최대값을 구할 때, 최소값으로 바꾸어야 함을 주의하자.

 

따라서 이 과정으로 segment tree를 이용하여 $diam$을 구하기 위해서 구간 $I$에 해당하는 노드에서

현재 depth

$\max(depth(v)) (v \in I)$

$\min(depth(v)) (v \in I)$

$\max(depth(v)-2depth(k)) (k \leq v \in I)$

$\max(depth(u)-2depth(k)) (u \leq k \in I)$

$\max(depth(u)-2depth(k)+depth(v)) (u \leq k \leq v \in I)>$

를 관리하면 되며, 쿼리가 들어올 때마다 leaf노드를 바꿔주고 부모노드로 올라가면서 update를 해주면 된다.

이 과정은 $O(log n)$만에 가능하다.

 

따라서 총 시간복잡도는 트리의 초기화 $O(n)$ 과 쿼리당 $O(log n)$으로 아래와 같다.

 

Time Complexity : $O(n+qlogn)$

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define lc(i) ((i)<<1)
#define rc(i) (((i)<<1)+1)
#define pa(i) ((i)>>1)
#define N 1<<19

using namespace std;

struct segnode
{
	int sum;
	int psummax; 
	int psummin;
	int leftmax;
	int rightmax;
	int diam;
} seg[N];

int n,q, p,l;
string s;
segnode merge(segnode x, segnode y)
{
	segnode ret;
	ret.sum = x.sum+y.sum;
	ret.psummax = max(x.psummax, x.sum+y.psummax);
	ret.psummin = min(x.psummin, x.sum+y.psummin);
	ret.leftmax = max( max(x.leftmax, y.leftmax-x.sum), x.psummax - (x.sum+y.psummin)*2);
	ret.rightmax = max( max(x.rightmax, y.rightmax-x.sum), x.sum+y.psummax - x.psummin*2);
	ret.diam = max( max(x.diam, y.diam), max(x.leftmax+x.sum+y.psummax, x.psummax+y.rightmax-x.sum));
	return ret;
}
segnode leaf(int x)
{
	segnode ret;
	ret.sum=x;
	ret.psummax= (x==1?1:0);
	ret.psummin= (x==1?0:-1);
	ret.leftmax= 1-x;
	ret.rightmax= 1;
	ret.diam =1;
	return ret;
}
void update(int x)
{
	seg[x+p] = (s[x]=='(')?leaf(1):leaf(-1);
	x+=p;
	while(x!=1)
	{
		x>>=1;
		seg[x] = merge(seg[lc(x)], seg[rc(x)]);
	}
}

void init()
{
	for(int i=0;i<l;i++) seg[i+p]= (s[i]=='(')?leaf(1):leaf(-1);
	for(int i=p-1;i>0;i--) seg[i]=merge( seg[lc(i)], seg[rc(i)]);
}
void printnode(int i)
{
	cout<<seg[i].sum<<" "<<seg[i].psummax<<" "<<seg[i].psummin<<" ";
	cout<<seg[i].leftmax<<" "<<seg[i].rightmax<<" "<<seg[i].diam<<" ";
	cout<<"\n";

}
int main()
{
	cin>>n>>q>>s;
	l=2*n-2;
	for(p=l;p^(-p&p);p+=(-p&p));
	
	init();
	cout<<seg[1].diam<<"\n";
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		--x,--y;
		swap(s[x],s[y]);
		update(x);
		update(y);
		cout<<seg[1].diam<<"\n";
	}
}