[BOJ] 13546 수열과 쿼리 4

 

 

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

13546번: 수열과 쿼리 4

알고리즘: Mo's (+ 평방 분할)

 

시간복잡도: $O((N+M)\sqrt N)$

---

Mo's 알고리즘과 관련된 문제들을 보면,

구간 [l, r]에서 특정 값이 몇 번 등장하는지를 구하는 문제들이 빈번히 등장한다.

push $A_i$: cnt[$A_i$]++

pop  $A_i$: cnt[$A_i$]--

이런 방식으로 말이다.

 

이를 응용하면 문제를 푸는 아이디어는 쉽게 생각해낼 수 있다.

$A_x=A_y$ 일 때, max(|x-y|) 를 구해야한다.

 

1. x-y의 값을 구해야하므로 우리는 index에 대한 정보를 가지고 있어야한다.

2. $A_i$를 push하고 pop를 하는 과정은 구간의 양끝에서 일어난다.

 

따라서, $A_i$를 push하고 pop할 때 $i$(index)를 추가해주거나 빼주면서 값들을 관리해주면 된다.

무턱대고 배열을 100000*100000 을 잡으면 메모리가 터져버릴테니 list를 이용하여 관리해준다.

(deque는 TLE를 받는다고 한다.)

 

 

그럼 끝....?

이면 이 문제가 solved.ac 기준 다이아5 일리가 없다 (...)

Mo's로 구간을 훑을 때, push만 한다면 |x-y|의 최댓값이 보장되지만 pop을 할 때도 있으므로,

$A_i$를 push, pop을 할 때 갱신되는 |x-y|의 값이 최대라는 보장이 없다.

그렇다고 무턱대고 cnt[|x-y|]++, cnt[|x-y|]-- 이런 식으로 |x-y| 값들을 관리해주면

최댓값을 구할 때 $O(N)$이 걸리므로 TLE를 받게 된다. 

 

그래서 |x-y|값도 $\sqrt N$씩 나눠, 버킷으로 관리해줘야한다.

그러면 최댓값을 구하는데 $O(\sqrt N)$이 걸리므로 제한시간 내 해답을 구할 수 있다.

 

---

사실, 평소에 구현하던 mo's 를 조금만 손보면 list와 평방 분할 없이 문제를 해결할 수 있다. 

 

핵심 아이디어는 구간을 따라가면서 원소를 하나씩 pop하는게 아니라 통째로 pop하는 것이다.

 

아래 그림처럼 두 가지의 case를 나눠서 통째로 pop해주면 $O(\sqrt N)$이 보장되면서 쿼리를 해결해줄 수 있다.

(Mo's 알고리즘에서 쿼리를 정렬하는 부분을 잘 살펴보면 왜 그런지 알 수 있을 것이다.)

 

연결된 칸들은 $\sqrt N$씩 나눈 하나의 버킷을 뜻하고, e는 다음 버킷의 시작지점이다. 

l, r 동일 버킷에 존재

 

 

l, r 다른 버킷에 존재

(자세한 설명은 pass)

간단하게 설명하자면 쿼리들이 동일한 버킷에 존재할 때, r은 점차 증가하고 l은 최대 $\sqrt N$씩만 변하므로

$O((M+N)\sqrt N)$만에 모든 쿼리들을 해결할 수 있다.

list의 추가 삭제 연산이나 max 값을 구할 때 평방 분할을 사용할 필요가 없으므로, 1번 풀이보다 속도가 훨씬 빠르다.

 

1번 풀이는 928ms (hilbert curve 이용)

2번 풀이는 320ms 정도 걸렸다. 

 

sol1) Mo's + sqrt decomposition

	// 13546: 수열과 쿼리 4
	#include<iostream>
	#include<algorithm>
	#include<cmath>
	#include<list>
	#define sz 320
	using namespace std;
	typedef long long ll;
	int N, M, K, l, r, d, t;//, sqrtN;
	int a[100001], ans[100001], cnt[100200], bcnt[sz];
	list<int> idx[100001];
	struct Q
	{
	int l, r, idx;
	ll d;
	bool operator < (const Q &a) const
	{
	//if (l/sqrtN != a.l/sqrtN) return l < a.l;
	//return r < a.r;
	return d < a.d;
	}
	}q[100001];
	ll convHilbert(int x, int y, int pow, int rotate)
	{
	if (!pow) return 0;
	pow--;
	int hpow = 1 << pow;
	int seg;
	if (x < hpow)
	{
	if (y < hpow) seg = 0;
	else seg = 3;
	}
	else
	{
	if (y < hpow) seg = 1;
	else seg = 2;
	}
	seg = (seg + rotate) & 3;
	int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	ll sq_size = ll(1) << (pow << 1);
	ll ans = seg * sq_size;
	ll add = convHilbert(nx, ny, pow, nrot);
	if (seg == 1 || seg == 2) ans += add;
	else ans += sq_size - add - 1;
	return ans;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	//sqrtN = sqrt(N);
	for (int i = 1; i <= N; ++i)
	cin >> a[i];
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q[i].l >> q[i].r;
	q[i].idx = i;
	q[i].d = convHilbert(q[i].l, q[i].r, 17, 0);
	}
	sort(q, q+M);
	l = q[0].l;
	r = l - 1;
	for (int i = 0; i < M; ++i)
	{
	while (l > q[i].l)
	{
	l--;
	t = a[l];
	if (!idx[t].empty())
	{
	d = idx[t].back() - idx[t].front();
	cnt[d]--;
	bcnt[d/sz]--;
	}
	idx[t].push_front(l);
	d = idx[t].back() - l;
	cnt[d]++;
	bcnt[d/sz]++;
	}
	while (r < q[i].r)
	{
	r++;
	t = a[r];
	if (!idx[t].empty())
	{
	d = idx[t].back() - idx[t].front();
	cnt[d]--;
	bcnt[d/sz]--;
	}
	idx[t].push_back(r);
	d = r - idx[t].front();
	cnt[d]++;
	bcnt[d/sz]++;
	}
	while (l < q[i].l)
	{
	t = a[l];
	d = idx[t].back() - idx[t].front();
	cnt[d]--;
	bcnt[d/sz]--;
	idx[t].pop_front();
	if (!idx[t].empty())
	{
	d = idx[t].back() - idx[t].front();
	cnt[d]++;
	bcnt[d/sz]++;
	}
	l++;
	}
	while (r > q[i].r)
	{
	t = a[r];
	d = idx[t].back() - idx[t].front();
	cnt[d]--;
	bcnt[d/sz]--;
	idx[t].pop_back();
	if (!idx[t].empty())
	{
	d = idx[t].back() - idx[t].front();
	cnt[d]++;
	bcnt[d/sz]++;
	}
	r--;
	}
	for (int j = 312; j >= 0; --j)
	{
	if (!bcnt[j]) continue;
	for (int k = 319; k >= 0; --k)
	{
	if (cnt[j*sz + k])
	{
	ans[q[i].idx] = j*sz + k;
	break;
	}
	}
	break;
	}
	}
	for (int i = 0; i < M; ++i)
	cout << ans[i] << "\n";
	return 0;
	}

view raw BOJ_13546.cpp hosted with ❤ by GitHub

 

 

sol2) Mo's reset

	// 13546: 수열과 쿼리 4
	#include<iostream>
	#include<algorithm>
	#include<cmath>
	using namespace std;
	typedef long long ll;
	int N, M, K, l, r, t, sqrtN;
	int a[100002], ans[100002], st[100001], en[100001], sub_ans;
	struct Q
	{
	int l, r, idx;
	ll d;
	bool operator < (const Q &a) const
	{
	if (l/sqrtN != a.l/sqrtN) return l < a.l;
	return r < a.r;
	}
	}q[100002];
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	sqrtN = sqrt(N);
	for (int i = 1; i <= N; ++i)
	cin >> a[i];
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q[i].l >> q[i].r;
	q[i].idx = i;
	}
	sort(q, q+M);
	q[M].l = q[M].r = N+1;
	int j = 0, e;
	for (int i = 0; i <= sqrtN + 1; ++i)
	{
	e = min((i+1)*sqrtN, N + 1);
	for (int k = i*sqrtN; k <= N; ++k) st[a[k]] = en[a[k]] = 0;
	while (q[j].l < e && q[j].r < e)
	{
	sub_ans = 0;
	for (int k = q[j].l; k <= q[j].r; ++k)
	{
	if (st[a[k]]) sub_ans = max(sub_ans, k - st[a[k]]);
	else st[a[k]] = k;
	}
	ans[q[j].idx] = sub_ans;
	for (int k = q[j].l; k <= q[j].r; ++k) st[a[k]] = 0;
	j++;
	}
	sub_ans = 0;
	l = e;
	r = e - 1;
	while (q[j].l < e)
	{
	while (q[j].r > r)
	{
	r++;
	if (st[a[r]])
	{
	sub_ans = max(sub_ans, r - st[a[r]]);
	en[a[r]] = r;
	}
	else en[a[r]] = st[a[r]] = r;
	}
	t = sub_ans;
	while (q[j].l < l)
	{
	l--;
	if (en[a[l]]) sub_ans = max(sub_ans, en[a[l]] - l);
	else en[a[l]] = l;
	}
	ans[q[j].idx] = sub_ans;
	sub_ans = t;
	while (l < e)
	{
	if (en[a[l]] < e) en[a[l]] = 0;
	l++;
	}
	j++;
	}
	}
	for (int i = 0; i < M; ++i)
	cout << ans[i] << "\n";
	return 0;
	}

view raw BOJ_13546_2.cpp hosted with ❤ by GitHub