2022.07.28. (Square Root Decomposition, Mo's Algorithm) 풀이

다룬 태그들

• 구간 나눠서 처리하기 (A)
• Square Root Decomposition (BC)
• Mo's Algorithm (DEF)

A. [20537] Gap (Platinum III)

Subtask 1은 간단히 해결할 수 있습니다.

\( a = 0, b = 10^{18} \)으로 놓은 뒤, \( f(a, b) \)를 호출하면 가장 작은 수와 가장 큰 수를 알 수 있게 됩니다.

그럼 그 가장 작은 수와 가장 큰 수를 제외하고 남은 \( N-2 \)개의 수에 대해 재귀적으로 탐색해주면 됩니다.

이는 \( a = mn+1, b = mx-1 \)로 범위를 조정시키면 됩니다.

그럼 배열의 모든 원소를 알 수 있게 되므로, 문제를 간단히 해결할 수 있습니다.

 

Subtask 2는 아래와 같이 해결할 수 있습니다.

우선 \( f(0, 10^{18}) \)을 호출해서 가장 큰 값과 가장 작은 값을 찾아봅시다.

이 두 수가 각각 \( mn, mx \)라고 하면, 문제의 답은 최소 \( \frac{mx-mn}{n-1} \)가 되어야 합니다.

 

그러니, \( [mn, mx] \) 구간에 있는 값들을 길이가 \( frac{mx-mn}{n-1} \)인 구간 \( n-1 \)개로 나눠볼 수 있습니다.

각 구간에서 답의 후보가 될 수 있는 값은 그 구간에서의 최솟값과 최댓값 뿐이므로, (중간에 있는 값들은 이전 수와 다음 수가 같은 구간에 있음, 즉 차이가 구간의 길이인 \( \frac{mx-mn}{n-1} \)를 넘을 수 없음)

각 구간에 대해 함수를 1번만 호출하면 정답으로써 가능한 후보를 모두 찾을 수 있습니다.

 

이 풀이가 만점을 받는 이유는, 우선 첫 호출은 비용이 \( N+1 \)이 듭니다.

그 뒤로, \( N-1 \)번의 호출 + 총 \( N \)개의 점이 호출 = \( 2N - 1 \)의 비용이 추가적으로 들게 됩니다.

그러니 총 비용은 \( N+1 + 2N-1 = 3N \)이 됩니다.

 

남은 건 그 후보들 중 실제로 길이가 가장 긴 점을 찾는 부분밖에 남지 않겠죠.

ll findGap(int T, int N){
    if (T == 1){
        ll mn = 0, mx = 1e18;
        int st = 1, ed = N;
        while (st <= ed){
            MinMax(mn, mx, &arr[st], &arr[ed]);
            mn = arr[st]+1; mx = arr[ed]-1;
            st += 1; ed -= 1;
        }
        ll ans = 0;
        for (int i = 1; i < N; i++){
            ans = max(ans, arr[i+1] - arr[i]);
        }
        return ans;
    }
    if (T == 2){
        ll mn = 0, mx = 1e18;
        MinMax(0, 1e18, &mn, &mx);
        vector<ll> v;
        ll gap = (mx-mn + N-2) / (N-1);
        for (int i = 1; i < N; i++){
            ll st = mn + (i-1)*gap;
            ll ed = st+gap - 1;
            ll mnv=0, mxv=0;
            MinMax(st, ed, &mnv, &mxv);
            if (mnv != -1){ v.push_back(mnv); }
            if (mxv != -1){ v.push_back(mxv); }
        }
        v.push_back(mx);
        int vl = v.size();
        ll ans = 0;
        for (int i = 1; i < vl; i++){
            ans = max(ans, v[i] - v[i-1]);
        }
        return ans;
    }
}

B. [18074] High Load Database (Platinum V)

편의상, \( A_{i} \)의 합을 \( X \)라고 하겠습니다.

 

어떠한 \( t \)에 대해, \( O(N) \) 시간에 간단히 문제를 해결할 수 있습니다.

이는 1번 원소를 넣은 뒤, 길이가 \( t \)를 넘어갈 때마다 새로운 batch를 만드는 방식으로 하면 됩니다.

하지만, 이걸 모든 경우에 대해 계산하는 건 힘들어 보입니다.

 

그런데, \( t \le \sqrt{X} \)에 대해서만 전처리를 돌린다면?

하나의 \( t \)에 대해 \( O(N) \)의 시간이 걸리니, \( O(N \sqrt{X}) \) 시간에 전처리를 끝내게 됩니다.

 

그럼 \( t > \sqrt{X} \)는 어떻게 할까요?

 

잠시 누적합을 생각해봅시다.

\( P_{i} = \sum_{j=1}^{i} A_{j} \)라고 하면,

batch를 빠르게 찾는 건, \( P_{i} \)에 대해서 \( P{j} \le P_{i} + t \)인 최대의 \( j \)를 빠르게 찾는 것이 됩니다.

그러니, \( C_{x} = (P_{i} = x) \)인 \( i \)가 존재하는가? 로 하나 정의해봅시다.

그럼 원래 누적합이 \( p \)까지였을 때 \( C_{x} = 1 \)인 \( x \le p + t \)를 빠르게 찾는 문제가 됩니다.

 

여기서 \( 0~X \)를 \( \sqrt{X} \)로 구간을 나눠보면, 하나의 \( \sqrt{X} \)의 구간에서 3개 이상의 점을 선택할 수 없음을 알 수 있습니다. (\( t > \sqrt{X} \)이므로, 중간 점을 건너뛸 수 있음)

그러니, \( C \)를 기준으로 Square Root Decomposition을 넣어준 뒤, 최댓값을 빠르게 찾아주면 됩니다.

(최댓값은 오른쪽에서 출발해서 Bucket에 후보가 존재하면 그 Bucket에서 최댓값을 찾아주는 방식으로 계산해주면 됩니다.)

const int SQ = 1024;
int arr[200020], prf[200020];

int ans[1000020];
int cnt[1000020], sqr[1020];

void Main(){
	int n; cin >> n;
	int mx = 0, sum = 0;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
		mx = max(mx, arr[i]); sum += arr[i];
	}
	for (int i = mx; i <= SQ; i++){
		ans[i] = 1; int num = 0;
		for (int j = 1; j <= n; j++){
			num += arr[j];
			if (num > i){ num = arr[j]; ans[i] += 1; }
		}
	}
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	for (int i = 0; i <= n; i++){
		cnt[ prf[i] ] += 1; sqr[ prf[i]>>10 ] += 1;
	}
	int q; cin >> q; while (q--){
		int x; cin >> x;
		if (x < mx){ cout << "Impossible" << endl; continue; }
		if (ans[x] != 0){ cout << ans[x] << endl; continue; }
		int st = 0;
		while (st < sum){
			int ed = min(sum, st+x), edp;
			while (~ed & 0x3ff){
				if (cnt[ed]){ goto done; }
				ed -= 1;
			}
			edp = ed>>10;
			while (sqr[edp] == 0){ edp -= 1; }
			ed = edp<<10 | 0x3ff;
			while (cnt[ed] == 0){ ed -= 1; }
			done: st = ed; ans[x] += 1;
		}
		cout << ans[x] << endl;
	}
}

C. [14504] 수열과 쿼리 18 (Diamond V)

수열을 \( \sqrt{N} \)개의 Bucket으로 나눈 뒤, 각 Bucket에 대해서 그 구간 내의 정렬된 수열을 들고 있어봅시다.

그럼 1번 쿼리는 평소에 Sqrt Decomposition 처리하듯이 처리해주면 됩니다.

 

2번 쿼리는 Bucket을 업데이트할 때 바뀌는 수를 제외하고는 이미 정렬이 되어있으니

삽입 정렬 비슷하게 바뀐 수만 왼쪽 / 오른쪽으로 이동시켜주면 \( O(\sqrt{N}) \)으로 해결할 수 있습니다.

int n, m, sqn;
int arr[100020]; vector<int> sqa[400];

void upd(int pos, int val){ int x = arr[pos]; int sqp = pos / sqn;
	auto idx = lower_bound(all(sqa[sqp]), x) - sqa[sqp].begin(); sqa[sqp][idx] = val;
	int len = sqa[sqp].size();
	while (idx > 0){
		if (sqa[sqp][idx-1] > sqa[sqp][idx]){ swap(sqa[sqp][idx-1], sqa[sqp][idx]); idx -= 1; }
		else{ break; }
	}
	while (idx+1 < len){
		if (sqa[sqp][idx] > sqa[sqp][idx+1]){ swap(sqa[sqp][idx], sqa[sqp][idx+1]); idx += 1; }
		else{ break; }
	}
	arr[pos] = val;
}
int qry(int st, int ed, int val){
	int res = 0;
	while (st <= ed){
		if ((st-1)/sqn != st/sqn){ break; }
		res += (arr[st] > val); st += 1;
	}
	while (st <= ed){
		if (ed/sqn != (ed+1)/sqn){ break; }
		res += (arr[ed] > val); ed -= 1;
	}
	if (st > ed){ return res; }
	int stp = st/sqn, edp = ed/sqn;
	for (int i = stp; i <= edp; i++){
		res += sqa[i].end() - upper_bound(all(sqa[i]), val);
	}
	return res;
}

void Main(){
	cin >> n; sqn = sqrt(n); m = n / sqn;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		sqa[i/sqn].push_back(arr[i]);
	}
	for (int i = 0; i <= m; i++){ sort(all(sqa[i])); }
	int q; cin >> q;
	while (q--){
		int typ; cin >> typ;
		if (typ == 1){
			int st, ed, x; cin >> st >> ed >> x;
			cout << qry(st, ed, x) << endl;
		}
		if (typ == 2){
			int pos, val; cin >> pos >> val;
			upd(pos, val);
		}
	}
}

D. [13547] 수열과 쿼리 5 (Platinum II)

Mo's 기본 문제입니다.

 

cnt[x]를 업데이트해가면서 답을 계산하면 되는데, 이 때 새로운 수가 등장하면 답에 1을 더하고

이미 있던 수의 개수가 0이 될 때는 답에 1을 빼주면 됩니다.

typedef pair<pii, int> piii;

int sq;
int arr[100020];
int cnt[1000020];
piii qry[100020];
int ans[100020];

bool cmp(piii a, piii b){
	if (a.fr.fr/sq != b.fr.fr/sq){ return a.fr.fr < b.fr.fr; }
	return a.fr.sc < b.fr.sc;
}

void Main(){
	int n;
	cin >> n;
	sq = sqrt(n);
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> qry[i].fr.fr >> qry[i].fr.sc;
		qry[i].sc = i;
	}
	sort(qry+1, qry+q+1, cmp);
	int st = 1, ed = 1; cnt[ arr[1] ] += 1;
	int res = 1;
	for (int i = 1; i <= q; i++){
		int pst = qry[i].fr.fr, ped = qry[i].fr.sc;
		int idx = qry[i].sc;
		for (int p = st; p < pst; p++){
			cnt[ arr[p] ] -= 1;
			if (cnt[ arr[p] ] == 0){ res -= 1; }
		}
		for (int p = pst; p < st; p++){
			cnt[ arr[p] ] += 1;
			if (cnt[ arr[p] ] == 1){ res += 1; }
		}
		for (int p = ed+1; p <= ped; p++){
			cnt[ arr[p] ] += 1;
			if (cnt[ arr[p] ] == 1){ res += 1; }
		}
		for (int p = ped+1; p <= ed; p++){
			cnt[ arr[p] ] -= 1;
			if (cnt[ arr[p] ] == 0){ res -= 1; }
		}
		st = pst; ed = ped;
		ans[idx] = res;
	}
	for (int i = 1; i <= q; i++){
		cout << ans[i] << endl;
	}
}

E. [13545] 수열과 쿼리 0 (Diamond IV)

합이 0이라는 건, 누적 합으로 나타낼 때 \( P_{ed} - P_{st-1} = 0 \), 즉 \( P_{ed} = P_{st-1} \)이라는 의미입니다.

그러니 구간에 있는 \( P_{i} \)를 저장해둔 뒤, 밑에 있는 13546번 문제처럼 풀어주면 됩니다.

int arr[100020], prf[100020];
const int DLT = 100020; deque<int> dq[200060];
pi3 qry[100020]; int ans[100020];

const int N = 262144; int seg[524290];
void upd(int pos, int typ){ int idx = prf[pos]+DLT;
	//cout << "UPDATE " << pos << ' ' << typ << endl;
	if (typ > 0){
		if (typ == 1){ dq[idx].push_front(pos); }
		else{ dq[idx].push_back(pos); }
		seg[idx+N-1] = dq[idx].back() - dq[idx].front();
	}
	else{
		if (typ == -1){ dq[idx].pop_front(); }
		else{ dq[idx].pop_back(); }
		if (dq[idx].empty()){ seg[idx+N-1] = 0; }
		else{ seg[idx+N-1] = dq[idx].back() - dq[idx].front(); }
	}
	idx += N-1; idx >>= 1;
	while (idx){
		seg[idx] = max(seg[idx<<1], seg[idx<<1|1]); idx >>= 1;
	}
	//cout << "RESULT "; for (int i = -4; i <= 4; i++){ cout << seg[i+DLT+N-1] << ' '; } cout << endl;
}

void Main(){
	int n; cin >> n; int sq = sqrt(n);
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	int q; cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> qry[i].fr.fr >> qry[i].fr.sc; qry[i].sc = i;
	}
	sort(qry+1, qry+q+1, [sq](pi3 a, pi3 b){
		if (a.fr.fr/sq != b.fr.fr/sq){ return a.fr.fr < b.fr.fr; }
		if (~(a.fr.fr/sq) & 1){ return a.fr.sc < b.fr.sc; }
		else{ return a.fr.sc > b.fr.sc; }
	});
	upd(0, 1);
	int st = 1, ed = 1; upd(1, 1);
	for (int qi = 1; qi <= q; qi++){
		int qst = qry[qi].fr.fr, qed = qry[qi].fr.sc;
		int qid = qry[qi].sc;
		while (qst < st){ st -= 1; upd(st-1, 1); }
		while (ed < qed){ ed += 1; upd(ed, 2); }
		while (st < qst){ upd(st-1, -1); st += 1; }
		while (qed < ed){ upd(ed, -2); ed -= 1; }
		//cout << "QUERY " << st << ' ' << ed << " = " << seg[1] << endl;
		ans[qid] = seg[1];
	}
	for (int i = 1; i <= q; i++){ cout << ans[i] << endl; }
}

F. [13546] 수열과 쿼리 4 (Diamond V)

각 수에 대해, deque로 그 수가 등장한 위치를 관리해봅시다. (인덱스는 정렬된 순서로!)

그럼, deque를 적절히 업데이트시키면 값이 고정되었을 때의 답을 빠르게 구할 수 있습니다.

 

실제 문제의 답은 수열에서의 max를 구하는 방식으로 하면 되며,

이는 \( C_{x} = (x = A_{i}) \)인 \( i \)의 개수 를 저장한 뒤,

맨 오른쪽에서부터 시작해서 Bucket에서 후보를 찾을 수 있다면: 그 구간에 답이 존재하니 탐색해주고

그렇지 않다면: Bucket 단위로 점프를 뛰어주면 됩니다.

int arr[100020];

int sq;
pi3 qrr[100020]; int ans[100020];

deque<int> dq[100020]; int res[100020];
int cnt[100020], sqc[321];
inline void upd(int pos, int num){ int sqp = pos / sq;
	int val = arr[pos];
	if (num == +1){ dq[val].push_front(pos); }
	if (num == +2){ dq[val].push_back(pos); }
	if (num == -1){ dq[val].pop_front(); }
	if (num == -2){ dq[val].pop_back(); }
	cnt[ res[val] ] -= 1; sqc[ res[val]/sq ] -= 1;
	res[val] = (dq[val].empty() ? 0 : dq[val].back() - dq[val].front());
	cnt[ res[val] ] += 1; sqc[ res[val]/sq ] += 1;
}

void Main(){
	int n, m; cin >> n >> m; sq = sqrt(n);
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int q; cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> qrr[i].fr.fr >> qrr[i].fr.sc; qrr[i].sc = i;
	}
	sort(qrr+1, qrr+q+1, [sq](pi3 p1, pi3 p2){
		if (p1.fr.fr/sq != p2.fr.fr/sq){
			return p1.fr.fr < p2.fr.fr;
		}
		return p1.fr.sc < p2.fr.sc;
	});
	cnt[0] += n; sqc[0] += n;
	int st = 1, ed = 1; upd(1, +1);
	for (int i = 1; i <= q; i++){
		int qs = qrr[i].fr.fr, qe = qrr[i].fr.sc;
		int qi = qrr[i].sc;
		while (qs < st){ st -= 1; upd(st, +1); }
		while (ed < qe){ ed += 1; upd(ed, +2); }
		while (st < qs){ upd(st, -1); st += 1; }
		while (qe < ed){ upd(ed, -2); ed -= 1; }
		int ptr = n/sq; while (ptr >= 0){
			if (sqc[ptr] > 0){
				int s = ptr*sq, e = min((ptr+1)*sq, n);
				for (int i = e-1; i >= s; i--){
					if (cnt[i] > 0){ ans[qi] = i; break; }
				}
				break;
			}
			ptr -= 1;
		}
	}
	for (int i = 1; i <= q; i++){ cout << ans[i] << endl; }
}