청정알고리즘

문제

https://www.acmicpc.net/problem/5698

풀이

한 줄을 입력 받아서 공백 뒤의 문자가 맨 앞 문자와 전부 같은지 체크한다.

Time Complexity : $O(|S|)$

코드

#include<iostream>
#include<string>
using namespace std;

int main() {
	while (1) {
		string s;
		int c=1;
		char x;
		getline(cin, s,'\n');
		if (s[0] == '*') break;

		for(int i=0;i<s.length();i++) if(s[i]>='A' && s[i]<='Z') s[i]=s[i]-'A'+'a';
		x=s[0]>='a'?s[0]-'a'+'A':s[0];
		for(int i=1;c!=0 && i<s.length();i++)
		{
			if(s[i-1]==' ')
			{
				if(s[i]==s[0]) continue;
				c=0;
			}
		}
		cout<<(c?"Y\n":"N\n");
	}
}

문제

https://www.acmicpc.net/problem/9521

풀이

Dynamic Programming과 DFS spanning tree에 대한 지식 모두를 요하는 문제라 어려울 수 있다.

우선 주어진 입력으로 주어지는 방향그래프가 어떤 모양일지 생각해보자.

주어진 그래프는 $n$개의 vertex와 $n$개의 edge로 이루어져 있다.

따라서 connected component 끼리 나눠도 각각의 component에 존재하는 vertex와 edge의 개수는 같다.

따라서 이 1개의 component에 대해서만 확인해 보자.

한 component는 $k$개의 vertex와 edge로 이루어져있는데, 이는 즉 DFS spanning tree를 만들면 남는 edge가 1개가 생기고 이 edge를 제거하면 전체 그래프는 tree가 된다는 것이다.

즉, 한개의 component는 중심이 되는 cycle이 하나가 존재하고, 이 cycle에 여러개의 tree가 달라붙어 있는 모양을 가지게 된다. 다음은 component의 예시이다.

전체 component를 색칠하는 경우의 수는 (사이클을 색칠하는 경우의 수) * (트리 부분을 색칠하는 경우의 수)이다.

따라서, 이 각각을 구한다면 원하는 경우의 수를 구할 수 있다.

우선 사이클 부분의 경우의 수를 구해보자.

$dp(n,k)=$($n$개의 칸에 $k$가지 색으로 칠할 때, 이웃한 색깔을 다르게 칠하면서, 첫번째 칸과 $n$번째 칸을 다르게 칠하는 경우의 수)

이 $dp$에 대한 점화식을 구하기 위해서 다음과 같이 경우를 나눠보자.

case 1) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 다를 경우

이 경우는 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-1,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하므로 $k-2$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-2) \times dp(n-1,k)$이다.

case 2) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 같을 경우

이 경우는 1번과 $n-1$번을 겹쳐서 cycle을 만든다고 생각하면, 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-2,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하는데, 두 색깔이 같으므로 $k-1$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-1) \times dp(n-2,k)$이다.

종합해보면 $dp(n,k)=(k-2) \times dp(n-1,k) + (k-1) \times dp(n-2,k)$이다.

여기서 초기값을 잘 생각해보아야 하는데, $n \geq 2$일 때에는 $dp$값과 구하고자 하는 사이클의 색칠 값이 같지만, $n=1$일 때에는 사이클의 색칠하는 경우의 수는 $k$이지만 $dp$값은 0이어야 한다.

따라서 $dp(1,k)=0, dp(2,k)=k^2-k$로 dp테이블을 먼저 채워준 후, $dp(1,k)=k$로 정의해야 한다.

다음은 트리 부분의 경우의 수를 구해보자.

이 부분은 어렵지 않은데, 각 노드들은 유일한 부모노드가 존재하며, 위에서부터 부모의 색깔과 다르게 칠하기만 해면 재귀적으로 칠할 수 있으므로, 각 칸마다 $k-1$가지의 색깔로 칠할 수 있다.

요약하자면 주어진 input에 $t$개의 component가 있고 각각의 component를 구성하는 cycle의 크기를 $c_i$라고 하면, 총 경우의 수는 다음과 같은 식으로 표현이 가능하다.

$$\prod_{i=1}^t dp(c_i,k) \times (k-1)^{(n-\sum_{i=1}^t c_i)}$$

cycle의 탐색은 DFS탐색을 하면서 visitTime을 관리하면 쉽게 할 수 있다.

출발한 노드의 visitTime과 도착한 노드의 visitTime을 비교했을 때, 출발한 노드의 visitTime이 더 크다면, 지금 도착한 노드는 이미 계산이 끝난 노드이므로 무시하고, 도착한 노드의 visitTime이 더 크다면 현재시간과 도착한 노드의 시간의 차이가 cycle의 크기가 된다.

따라서 시간복잡도는 $dp$ 테이블을 채우는데 $O(n)$, DFS를 하면서 cycle 부분의 색칠 수를 곱하는데에 $O(n)$ 나머지 트리 부분의 색칠 수를 곱하는데에 $O(n)$(이 부분은 $O(logn)$에도 가능하지만 bottleneck이 아니므로 무시)으로, 총 시간복잡도는 $O(n)$이다.

Time Complexity : $O(n)$

코드

#include<iostream>
#include<algorithm>
#define N 1000004
#define MOD 1000000007

using namespace std;

int n,k;
int a[N],t[N];
typedef long long ll;
ll dp[N];
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];

	dp[0]=k;
	for(int i=2;i<=n;i++) dp[i] = (dp[i-1]*(k-2)+dp[i-2]*(k-1))%MOD;
	dp[1]=k;
    
	int c=1,cnt=0;
	ll ans=1;

	for(int i=1;i<=n;i++)
	{
		if(t[i]!=0)continue;
		int j=i;
		for(;t[j]==0; j=a[j]) t[j]=c++;
		if(t[j]>=t[i])
		{
			int x = c-t[j];
			ans = (ans*dp[x])%MOD;
			cnt += x;
		}
	}
	for(int i=n-cnt;i>0;i--) ans = (ans * (k-1))%MOD;
	cout<<ans;
}

문제

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

풀이

shift 연산과 더하기 빼기를 이용하여 나누기를 해본다.

우선 절댓값을 취해서 부호부분을 제외한 나머지 부분만 계산할 것인데, 이때 INT_MIN의 경우 절대값을 하면 넘어가므로, INT_MIN에 대한 처리를 진행한다.

지금 답을 출력할 수 있는 것은 출력하고, 아니라면 divisor를 한번 더해줘서 미리 한번의 덧셈을 진행해놓는다.

이제 $x/y$를 계산하는데 $b$라는 변수를 초기값 1로 따로 관리를 한다.

기본적인 알고리즘은 다음과 같다.

case 1) $x\leq y*b$

x에서 y*b를 빼내고, $ans$에 b를 더해준다. 그 후, b에 2를 곱한다.

이 때, y*b가 INT_MAX보다 커지려고 하면 곱하지 않는다.

case 2) else

이때, x가 처음의 divisor보다 작아졌을 경우, 다 나눴으므로 반복문을 종료한다.

아니라면, b에 2를 나눈다.

이 과정을 반복하면, $O(log n)$의 시간복잡도로 나누기를 할 수 있다. 

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int divide(int dividend, int divisor) {
        int ans=0;
        if(divisor==INT_MIN) return dividend==INT_MIN?1:0;
        if(dividend==INT_MIN)
        {
            if(divisor==-1) return INT_MAX;
            if(divisor==1) return INT_MIN;
            ans++;
            dividend+=abs(divisor);
        }
            
        int x=abs(dividend);
        int y=abs(divisor);
        bool sgn = (dividend<0)^(divisor<0);
        int b=1;
        while(x>0)
        {
            if(x>=y)
            {
                x-=y;
                ans+=b;
                if(y>>30) continue;
                b<<=1;
                y<<=1;
            }
            else
            {
                if(divisor>x) break;
                b>>=1;
                y>>=1;
            }
        }
        return sgn?-ans:ans;
    }
};

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

풀이

문자열 내에 특정 문자열이 있는지 찾는 알고리즘으로 kmp 알고리즘이 유명하다.

이를 이용한다. 

Time Complexity : $O(n+m)$

코드

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if(nl==0) return 0;
        
        vector<int> fail;
        fail.resize(nl,0);
        int j=0;
        for(int i = 1; i< nl ; i++)
        {
            while(j > 0 && needle[i] != needle[j]) j = fail[j-1];
            if(needle[i] == needle[j]) fail[i] = ++j;
        }
        j=0;
        for(int i=0;i<hl;i++)
        {
            while(j>0 && haystack[i] != needle[j]) j = fail[j-1];
            if(haystack[i] == needle[j])
            {
                if(j==nl-1) return i-nl+1;
                else j++;
            }
        }
        
        return -1;
    }
};

문제

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

풀이

two pointer를 이용하여 문제를 푼다.

선행 포인터가 val이랑 다를 경우 후행 포인터의 칸에 순차적으로 채워준다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0;
        for(int j=0;j<nums.size();j++)
            if(nums[j]!=val)nums[i++]=nums[j];
        return i;
    }
};

문제

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

풀이

unique 함수를 이용하여 계산한다.

직접 구현하려면 two pointer를 이용해서 구해보자. 어렵지 않다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return unique(nums.begin(), nums.end())-nums.begin();
    }
};

문제

https://www.acmicpc.net/problem/1734

풀이

DFS를 탐색하면서 각 노드 별로 다음 정보를 저장한다.

• sTime : 노드를 처음 만났을 때의 시간
• eTime : 자식 노드의 탐색을 모두 끝내고 노드를 빠져나올 때의 시간
• low : 해당 노드에서 DFS를 진행했을 때, 등장하는 노드들의 sTime의 최솟값
• depth : DFS spanning tree에서의 depth
• par : DFS spanning tree에서의 부모 노드
• adj : 인접리스트, 현재 노드와 연결된 노드의 정보
• child : DFS spanning tree에서의 자식 노드들

이제 쿼리를 분석해보자.

1) 1번 쿼리, $a,b,g_1,g_2$가 입력으로 들어온다.

만약 $g_1,g_2$가 DFS spanning tree의 tree edge가 아니라면, $a,b$는 DFS spanning tree로 연결된다.

일반성을 잃지 않고 $g_1$이 $g_2$의 parent라고 하자.

이 때, $g_1, g_2$ edge가 단절선이 아니면, 즉 $g_2$에서 $g_2$위로 가는 bypass가 있으면 그 bypass로 연결이 가능하다.

만약 $g_1, g_2$가 단절선이라면, $a,b$가 단절선을 기준으로 같은 쪽에 있는지를 확인하고, 같은 쪽에 있으면 단절 후에도 연결이 가능하다.

위의 경우가 모두 불가능하다면, $a,b$ 사이의 경로는 단절선을 통하는 경로 뿐이고 단절선을 끊으면 이동할 수 없다.

각각의 체크는 모두 $O(1)$만에 가능하다.

2) 2번 쿼리, $a,b,c$가 입력으로 들어온다.

만약 $a,b$가 둘 모두 DFS spanning tree 상에서 $c$의 자손이 아니라면, tree의 정의에 의해 c를 통하지 않는 $a$와 $b$사이의 경로가 존재한다.

만약 둘 모두 $c$의 자손이라면, $c$의 자식들 중에서 $a$와 $b$를 각각 포함하는 자식이 존재할 것이다.

이를 $ac, bc$라고 하자. ($a=ac, b=bc$일 수도 있다.)

만약 $ac=bc$라면 $c$가 $ac, bc$의 lca(lowest common ancestor)가 아니라는 뜻이므로, c가 없어져도 a와 b사이의 경로가 존재한다.

만약 위의 경우가 아니라면 $a,b$중 $c$의 자손인 노드는 $c$를 우회해서 갈수 있는지 체크하고, 자손이 아닌 노드끼리는 단절의 전후 상관없이 항상 연결이 가능하므로 자손인 노드만 $c$보다 빠른 점으로 가는 bypass가 있는지 확인해주면 된다.

각각의 처리는 대부분 $O(1)$에 가능하지만, $ac,bc$를 찾기 위해서 $c$의 child 목록에서 binary search를 통해 해당하는 child를 찾아야하므로 $O(log(\text{# child of c}))$만큼의 시간복잡도가 필요하고, 이는 최대 $O(logn)$ 만큼 필요하다.

Time Complexity : $O(n+q_1+q_2logn)$

코드

#include<iostream>
#include<vector>

using namespace std;

struct data
{
	int sTime;
	int eTime;
	int low;
	int depth;
	int par;
	vector<int> adj;
	vector<int> child;
};
vector<data> info;

int n,e,q;
int visitTime = 1;
void dfs(int now)
{
	data& d=info[now];
	d.sTime = d.low = visitTime++;
	for(vector<int>::iterator it=d.adj.begin();it!=d.adj.end();++it)
	{
		int nxt = *it;
		data& x = info[nxt];
		if(x.depth!=-1)
		{
			if(d.par!=nxt) d.low = min(d.low, x.sTime);
			continue;
		}
		x.depth = d.depth+1;
		x.par = now;
		d.child.push_back(nxt);
		dfs(nxt);
		d.low = min(d.low, x.low);
	}
	d.eTime = visitTime++;
}

bool isAncestor(int x1, int x2)
{
	return info[x1].sTime<=info[x2].sTime && info[x2].eTime <=info[x1].eTime;
}
bool bypass(int x1,int x2)
{
	return info[x1].low<info[x2].sTime;
}

int findChild(int x1, int x2)
{
	int l=0,r=info[x1].child.size()-1;
	while(l!=r)
	{
		int mid = (l+r)>>1;
		int now = info[x1].child[mid];
		if(info[x2].sTime > info[now].eTime) l=mid+1;
		else if(info[x2].eTime < info[now].sTime) r = mid-1;
		else return now;
	}
	return info[x1].child[l];
}
void yes()
{
	cout<<"yes\n";
}
void no()
{
	cout<<"no\n";
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n>>e;

	data init={0,0,0,-1,0,vector<int>(),vector<int>()};
	info.resize(n+1,init);
	while(e--)
	{
		int x,y;
		cin>>x>>y;
		info[x].adj.push_back(y);
		info[y].adj.push_back(x);
	}
	
	info[1].par = -1;
	info[1].depth = 1;

	dfs(1);

	cin>>q;
	while(q--)
	{
		int x,a,b;
		cin>>x>>a>>b;
		if(x==1)
		{
			int g1,g2;
			cin>>g1>>g2;
			if(isAncestor(g2,g1)) swap(g1,g2);

			if(info[g1].depth != info[g2].depth-1) yes();
			else if(bypass(g2,g2)) yes();
			else if(isAncestor(g2,a)==isAncestor(g2,b)) yes();
			else no();
		}
		else
		{
			int c;
			cin>>c;
			if(!isAncestor(c,a) && !isAncestor(c,b)) yes();
			else if(isAncestor(c,a) && isAncestor(c,b))
			{
				int ac = findChild(c,a);
				int bc = findChild(c,b);
				if(ac==bc)yes();
				else if(bypass(ac,c)&&bypass(bc,c)) yes();
				else no();
			}
			else
			{
				if(!isAncestor(c,a)) swap(a,b);
				int ac = findChild(c,a);
				if(bypass(ac,c)) yes();
				else no();
			}
		}
	}
}

문제

https://www.acmicpc.net/problem/1849

풀이

세그먼트 트리를 1로 모두 채운 다음, 숫자의 입력을 쿼리라고 생각하자.

i번째 쿼리로 x가 들어왔을 경우, 현재 prefix sum이 x+1인 점중 가장 작은 점을 찾아서 그 칸을 채우면 된다. 

예를 들어서 $n=8$인 경우 첫번째 쿼리로 5가 들어온 경우 현재 세그먼트 트리는 다음과 같이 구성된다.

그 후 다음과 같이 segment tree를 업데이트 해준다.

이 때, 저 prefix sum이 5가 되는 부분을 찾아야 하는데, 이는 거꾸로 segment tree의 꼭대기 부터 내려오면서 찾을 수 있다.

만약 left child의 sum이 v보다 작거나 같다면 원하는 index는 오른쪽 자식에 있으며, left child의 sum이 v보다 크다면 원하는 index는 왼쪽 자식에 있다.

이러한 방법으로 leaf node까지 도착하면, 도착한 노드에 원하는 숫자를 추가해주면 된다.

이 방법으로 쿼리마다, node를 찾는데 $O(log n)$, 세그먼트 트리를 업데이트 해주는데 $O(log n)$이 걸린다.

따라서 총 시간복잡도는 $O(n+qlogn)$이다.

Time Complexity : $O(n+qlogn)$

코드

#include<iostream>
#include<vector>
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

int seg[1<<18];
int n,p;
vector<int> ans;
void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = seg[lc(t)]+seg[rc(t)];
	}
}
int loc(int t)
{
	int r=1;
	while(r<p)
	{
		if(t>=seg[lc(r)])
		{
			t-=seg[lc(r)];
			r=rc(r);
		}
		else r=lc(r);
	}
	return r-p;
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n;

	ans.resize(n);
	for(p=n;p^(-p&p);p+=(-p&p));
	for(int i=p;i<p+n;i++) seg[i]=1;
	for(int i=p-1;i>0;i--) seg[i]= seg[i<<1]+seg[i<<1|1];

	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int l=loc(x);
		seg[p+l]=0;
		ans[l]=i;
		update(l);
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<" ";
}

문제

https://www.acmicpc.net/problem/17163

풀이

만약 mod가 query개수 보다 많다면 항상 불가능하므로, -1을 출력한다.

mod가 query개수보다 작은 경우에는 0~mod-1까지의 index를 가지는 stack을 만들어보자.

그리고 숫자가 새로 들어올때 마다, 해당하는 나머지를 index로 가지는 stack에 현재 arr의 원소의 개수를 넣어준다.

3 query가 들어왔을 때, 각 나머지 별로 stack의 top에 있는 숫자의 min값이 우리가 찾는 index가 되고, 전체 사이즈에서 찾은 값을 빼주면 답이 된다.

이 방식으로 구하면 $O(q\times mod)$의 시간복잡도가 걸리지만 segment tree를 이용하면 $O(mod+q log mod)$의 시간복잡도로 원하는 답을 구할 수 있다.

Time Complexity : $O(mod+q log mod)$

코드

#include<iostream>
#include<vector>
#include<stack>
#define N 1000000
#define INF 1<<30
using namespace std;

stack<int, vector<int> > S;
stack<int, vector<int> > rem[N];

int seg[1<<21];
int p, q, mod;

void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = min(seg[t<<1], seg[t<<1|1]);
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>q>>mod;
	for(p=mod;p^(-p&p);p+=(-p&p));

	if(mod>q)
	{
		while(q--)
		{
			int x;
			cin>>x;
			if(x==3) cout<<-1<<"\n";
			if(x==1) cin>>x;
		}
		return 0;
	}

	for(int i=p;i<p<<1;i++) seg[i]=i<p+mod?-1:INF;
	for(int i=p-1;i>0;i--) seg[i] = min(seg[i<<1],seg[i<<1|1]);
	while(q--)
	{
		int x;
		cin>>x;
		if(x==1)
		{
			cin>>x;
			int t=x%mod;
			S.push(t);
			rem[t].push(S.size());
			seg[p+t]=S.size();
			update(t);
		}
		else if(x==2)
		{
			if(S.empty())continue;
			int t = S.top();
			S.pop();
			rem[t].pop();
			seg[p+t]=rem[t].empty()?-1:rem[t].top();
			update(t);
		}
		else
		{
			if(seg[1]==-1) cout<<"-1\n";
			else cout<< S.size()-seg[1]+1<<"\n";
		}
	}
}

문제

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

풀이

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

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