청정알고리즘

문제

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

풀이

전형적인 Convex Hull 문제이다.

아래 풀이에서는 Graham Scan이라고 하는 $O(nlogn)$의 알고리즘을 사용한다.

Convex Hull을 구한 후, Convex Hull 상에서 가장 먼 두 점을 찾는데, 원래는 Rotating Calipers 라는 알고리즘을 사용하여 $O(n)$에 구해야 한다.

하지만 필자는 한 번도 구현해본 적이 없고, 실제 이 문제에서는 좌표의 범위가 작고, 정수점만 입력으로 들어오기때문에 Convex Hull의 점의 수가 매우 작고, 실제로 1000*4=4000개보다 작음은 약간의 논증을 통해 보일 수 있다.

따라서 Convex Hull 내부의 모든 점을 비교해도 시간안에 구할 수 있다.

정해는 rotating calipers라는 알고리즘을 이용해서 가장 먼 두 점을 구하는데 $O(|convex hull|)$이면 충분하다.

Time Complexity : $O(nlogn + |convex hull|^2)$

코드

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pos;
 
double dist(pos p1, pos p2)
{
	double dissq = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
	return sqrt(dissq);
}

int n;

vector<pos> p;

ll ccw(pos p1, pos p2, pos p3)
{
	return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
}

bool cmp(pos p1, pos p2)
{
	ll c = ccw(p[0], p1, p2);
	if (c > 0) return 1;
	if (c < 0) return 0;
	else
    {
		if (dist(p[0], p1) < dist(p[0], p2)) return 1;
		else return 0;
	}
}

int main()
{
	cin>>n;

	p.resize(n);
	for (int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
	
	sort(p.begin(),p.end());
	sort(p.begin()+1,p.end(),cmp);
    
	vector<pos> cvxh;
	cvxh.push_back(p[0]);
	cvxh.push_back(p[1]);

	for (int i=2;i<n;i++)
	{
		while (cvxh.size() >= 2 && ccw(cvxh[cvxh.size()-2],cvxh.back(),p[i])<=0)
			cvxh.pop_back();
		cvxh.push_back(p[i]);
	}
    
	double ans=-1;
	int len=cvxh.size();
	for (int i=0;i<len;i++) for (int j=i+1;j<len;j++)
		ans=max(ans, dist(cvxh[i], cvxh[j]));

    printf("%.10f", ans);
}

문제

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

풀이

$x,y$가 input으로 들어올때, $f(x)=$(1부터 $x$까지 적었을 때, 나타나는 0~9의 숫자의 배열)이라고 정의하자.

그럼 구하고자 하는 정답은 $f(y)-f(x-1)$이 된다.

그럼 $f(x)$는 어떻게 구할까?

자릿수별로 각 숫자의 개수를 계산한다는 아이디어를 기본적으로 생각해보자.

즉, 1의 개수를 셀때, 1의 자리에 오는 1, 10의 자리에 오는 1, 100의 자리에 오는 1,....들을 모두 세서 더해준다면 구하고자하는 전체 1의 개수를 구할 수 있을 것이다.

결국 위의 질문은 1~x까지의 숫자중 $10^t$자리가 $a$인 숫자가 모두 몇개인지를 각 $t$에 대해 모두 풀어서 더해주면 된다.

이는 다음과 같이 경우를 나누어 풀수 있다.

case 1) $a$가 $x$의 $10^t$자리 숫자보다 작을 경우

예를 들어서 $x=12345, a=1, 10^t=100$인 경우를 보자.

그러면 ??1?? 꼴의 숫자가 몇 개인지를 세는 것인데, 이는 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류) * 100이 된다.

또한 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류)는 위의 예시에서는 0부터 12까지이므로, 총 13개가 가능하다.

즉 1??, 11??, 21??, 31??, ... , 121??의 경우가 가능하다는 뜻이다.

수식으로 나타내면 $(x/10^{t+1}+1)\times 10^t$가지 경우임을 알 수 있다.

case 2) $a$가 $x$의 $10^t$자리 숫자와 같을 경우

$x=12345, a=3, 10^t=100$을 예로 들어보자.

이 경우에는 3??, 13??, ..., 113??까지는 자유롭게 가능하고, 123??의 경우에는 0~45까지 총 46개만 가능하다.

같은 방식으로 수식으로 나타내면 $(x/10^{t+1})\times 10^t+(x%10^t)+1$ 가지 경우가 있음을 알 수 있다.

case 3) $a$가 $x$의 $10^t$자리 숫자보다 클 경우

비슷한 방식으로  $x=12345, a=5, 10^t=100$을 예로 들어보자.

이 경우에는 5??, 15??, ..., 115??까지만 가능하므로 case 1)의 경우보자 $10^t$개 적게 된다.

따라서 이 경우는 $(x/10^{t+1})\times 10^t$ 가지이다.

따라서 이를 모두 각각 더해주면 된다.

주의할 점은 맨 앞자리에 0이 올수는 없으므로 0은 각 경우에서 $10^t$개만큼 빼주어야 한다는 점이다.

즉 10?? 꼴의 숫자는 있지만, 0?? 꼴의 숫자는 존재하지 않으므로, 이 경우를 빼주는 것이다.

위와 같은 방식으로 0~9까지 등장수를 모두 더해주면 $f(x)$를 구할 수 있다.

Time Complexity : $O(logx+logy)$

코드

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

vector<int> f(int t)
{
	vector<int> ret(10);
	for(int i=1;i<=t;i*=10)
	{
		for(int j=0;j<10;j++)
		{
			if( j<(t/i)%10) ret[j] += (t/(i*10)+1)*i;
			else if( j==(t/i)%10 ) ret[j] += (t/(i*10))*i+(t%i)+1;
			else ret[j] += (t/(i*10))*i;
		}
		ret[0]-=i;
	}
	return ret;
}
int main() {
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0 && y==0)break;
		vector<int> a1 = f(y);
		vector<int> a2 = f(x-1);
		for(int i=0;i<10;i++)
		{
			cout<<a1[i]-a2[i]<<" ";
		}
		cout<<"\n";
	}
}

문제

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

풀이

단순히 생각하면 30000 * 30000 배열을 만들어 사각형이 입력으로 들어오면 해당 사각형의 영역에 1씩 더해준다.

그 후, 1이상의 값을 가지는 모든 칸의 값을 세주면 된다.

하지만 이와 같은 방법으로는 시간도 많이 소모하고, 공간도 많이 잡는다.

따라서 line sweeping 알고리즘을 사용하여 현재 line과 닿아있는 부분의 30000개 배열만 생각한다.

세로 선을 왼쪽 끝부터 오른쪽 끝까지 sweeping한다고 생각하자.

sweeping하면서 만나는 면적을 모두 더하면 구하고자 하는 정답이 된다.

sweeping 하면서 발생하는 event의 종류가 두 가지인데, 각각에 대해서 처리해 주면 된다.

case 1) 새로운 사각형의 등장

이 때는 현재 직사각형의 왼쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 증가시켜준다.

case 2) 사각형의 퇴장

이 때는 현재 직사각형의 오른쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 감소시켜준다.

위와 같은 과정을 거치면서 현재 line에 있던 1이상의 칸의 수를 모두 더해주면 된다.

하지만 이렇게 되면 $O(nC)$의 시간복잡도로 시간안에 통과할 수 없다.

따라서 전체 구간의 합을 segment tree를 이용하여 관리해주면 된다.

이 때, 등장하는 쿼리는 구간에 1을 더해주는 query이므로, lazy propagation의 아이디어를 사용한다.

lazy propagation처럼 게으르게 값을 관리하는데, 현재 구간이 전파될 예정이라면, 하위 노드의 값과 관계 없이 이 구간은 모두 값을 구하는데 사용되게 된다.

root 노드로 부터 내려가다가 처음으로 전파될 예정인 노드를 만나면 바로 그 하위 구간의 길이를 return해주면 되기 때문에, 전파과정은 진행하지 않아도 무방하다.

이러한 방법을 이용하여 segment tree를 업데이트 해주면, event마다 log 시간복잡도에 원하는 작업을 완료할 수 있다.

Time Complexity : $O(N(logN+logC))$

코드

#include<iostream>
#include<algorithm>
#define N 10005
#define C 40000
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

struct ev
{
	int x, y1, y2, z;
	bool operator<(const ev & t)
	{
		return x<t.x;
	}
}evt[N<<1];

ev make_ev(int X, int Y1, int Y2, int Z)
{
	ev r;
	r.x=X;
	r.y1=Y1;
	r.y2=Y2;
	r.z=Z;
	return r;
}
struct segtree
{
	int val;
	int num;
} seg[C<<2];

int n,pr,ans;

void update(int l, int r, int v, int t, int x, int y)
{
	if(y<l || r<x) return;
	if(l<=x && y<=r) seg[t].num+=v;
	else
	{
		int mid=(x+y)>>1;
		update(l,r,v,lc(t),x,mid);
		update(l,r,v,rc(t),mid+1,y);
	}
	if(seg[t].num) seg[t].val=y-x+1;
	else seg[t].val=(x==y?0:seg[lc(t)].val+seg[rc(t)].val);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;

		evt[i]=make_ev(a,b,d-1,1);
		evt[i+n]=make_ev(c,b,d-1,-1);
	}
	sort(evt,evt+2*n);
	for(int i=0;i<2*n;i++)
	{
		if(i>0) ans+=(evt[i].x-pr)*seg[1].val;
		update(evt[i].y1, evt[i].y2, evt[i].z,1,0,C);
		pr=evt[i].x;
	}
	cout<<ans;
}

문제

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

풀이

우선 flood fill을 이용하여 각 섬별로 넘버링을 한다.

같은 방법으로 0,0 구석의 물에서부터도 flood fill을 이용하여 안전한 바다를 전부 구할것이다.

flood fill을 할때, 4방향, 즉 상하좌우의 경우 인접한 바다를 모두 queue에 추가한다.

또한 추가적으로 대각선방향 4방향에서도 안전한 바다로 전파될 수 있는 바다들이 존재한다.

만약

#.

.#

모양처럼 대각선으로만 뚫려있고 상하로 막혀있지만, 왼쪽의 섬과 오른쪽의 섬이 서로 다른 섬이라면 사냥꾼은 두 섬에 동시에 존재할 수 없으므로, 둘 중 사냥꾼이 없는 쪽으로 빠져나올 수 있다.

따라서 대각선으로만 뚫려있어도 위의 조건에 해당한다면 queue에 추가해준다.

이 과정을 진행하면서 안전한 바다와 인접한 땅들을 모두 체크해주어 'O'로 바꾸고, 나머지를 'X'로 바꾸면 문제를 해결할 수 있다.

Time Complexity : $O(nm)$

코드

#include<iostream>
#include<string>
#include<queue>
#define N 2004

using namespace std;
typedef pair<int,int> pi;
string s[N];
int mp[N][N],n,m,color;
pi flag[4]={pi(1,0),pi(0,1),pi(-1,0),pi(0,-1)};
vector<char> ans;

pi operator+(const pi &x1, const pi &x2)
{
	return make_pair(x1.first+x2.first, x1.second+x2.second);
}

bool cango(pi t)
{
	return t.first>=0 && t.first<n && t.second>=0 && t.second<m;
}

void floodFillLand(pi st, int v)
{
	mp[st.first][st.second]=v;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			vector<int> V;

			if(!cango(next) || mp[next.first][next.second]!=0) continue;

			if(s[next.first][next.second]=='#')
			{
				mp[next.first][next.second] = v;
				Q.push(next);
			}
		}
	}
}

void floodFillWater(pi st)
{
	mp[st.first][st.second]=-1;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			if(!cango(next)) continue;
			if(mp[next.first][next.second]>0)
			{
				ans[mp[next.first][next.second]]='O';
				continue;
			}

			if(mp[next.first][next.second]==0 && s[next.first][next.second]=='.')
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}

		for(int k=0;k<4;k++)
		{
			pi next= f+flag[k]+flag[(k+1)&3];
			pi c1 = f+flag[k];
			pi c2 = f+flag[(k+1)&3];
			if(!cango(next) || s[next.first][next.second]=='#') continue;

			if(mp[next.first][next.second]!=-1 && mp[c1.first][c1.second]>0
				&& mp[c2.first][c2.second]>0 && mp[c1.first][c1.second]!=mp[c2.first][c2.second])
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];

	color=0;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(mp[i][j] || s[i][j]=='.') continue;
		floodFillLand(make_pair(i,j),++color);
	}

	ans.resize(color+1,'X');
	floodFillWater(make_pair(0,0));

	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(s[i][j]=='.')continue;
		s[i][j] = ans[mp[i][j]];
	}

	for(int i=0;i<n;i++) cout<<s[i]<<"\n";
}

문제

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

문제

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