[Algorithm] cpp 백준 13545번: 수열과 쿼리 0

문제

링크: 백준 13545번 수열과 쿼리 0
요약: 길이 N의 수열 A(각 원소는 1 또는 -1)와 M개의 구간 [i, j]가 주어질 때, 각 구간 안에서 합이 0인 가장 긴 연속 부분수열의 길이를 구한다.
제한: N, M ≤ 100,000

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
입력
6
1 1 1 -1 -1 -1
4
1 3
1 4
1 5
1 6

출력
0
2
4
6

접근 개요

핵심 관찰: 누적합 S[k] = A[1]+…+A[k]라 하면, 부분합 A[x+1..y] = 0 ⇔ S[x] = S[y].
즉, 질의 [i, j]는 누적합 배열의 구간 [i-1, j]에서 같은 값이 등장하는 인덱스쌍의 최대 거리(max(y−x))를 묻는 문제로 환원된다.
온라인 최대거리 관리를 위해 각 질의를 Mo 알고리즘으로 오프라인 정렬하고, 현재 창(window) 내에서 값별 인덱스 등장 위치를 deque로 유지한다.
각 값의 span(맨뒤−맨앞)을 갱신하며, 길이별 빈도(cntLen)와 버킷을 이용해 최대 span을 O(1) 가깝게 질의한다.

flowchart LR
    A[원배열 A(±1)] --> B[누적합 S]
    B --> C[[쿼리 [i,j] → S에서 [i-1, j]]]
    C --> D{Mo 정렬}
    D --> E[값별 인덱스 deque 유지]
    E --> F[각 값의 span = back - front]
    F --> G[길이별 카운팅/버킷]
    G --> H[최대 span = 정답]

알고리즘

전처리: 누적합 S[0..N] 계산 후 좌표압축.
질의 변환: [i, j] → S의 구간 [i-1, j].
Mo 알고리즘: 구간을 이동하며 아래 연산을 수행한다.
- 왼쪽/오른쪽에 인덱스 추가/삭제 시, 해당 값의 deque 앞/뒤에 넣거나 빼고, 이전 span과 새로운 span을 길이 카운터에 반영한다.
- 길이 카운터는 cntLen[0..N]와 sqrt 버킷으로 관리하여 현재 최대 길이를 빠르게 찾는다.

정당성(스케치)

S[x] = S[y] ⇔ A[x+1..y]의 합이 0. 따라서 [i-1, j]에서 동일한 누적합 값의 가장 먼 두 위치의 차이가 곧 최장 0-합 부분수열의 길이이다.
창 크기가 변할 때마다 각 값의 front/back만이 span을 결정하므로 deque로의 상수 시간 갱신이 가능하다.
전 구간의 최대 길이는 길이별 빈도를 통해 상수에 가까운 시간으로 얻을 수 있다.

복잡도

시간: O((N + M) · √N) 수준 (Mo 이동 총량 × O(1) 갱신/질의)
공간: O(N) (좌표압축, 위치 deque, 길이 카운터)

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Query {
	int L, R, idx;
	int block;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	if (!(cin >> N)) return 0;
	vector<int> A(N + 1);
	for (int i = 1; i <= N; ++i) cin >> A[i];

	// Prefix sums S[0..N]
	vector<int> pref(N + 1, 0);
	for (int i = 1; i <= N; ++i) pref[i] = pref[i - 1] + A[i];

	// Coordinate compression of prefix sums
	vector<int> all = pref;
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	int K = (int)all.size();
	vector<int> idOfIndex(N + 1);
	for (int i = 0; i <= N; ++i) {
		idOfIndex[i] = int(lower_bound(all.begin(), all.end(), pref[i]) - all.begin());
	}

	int M; cin >> M;
	vector<Query> qs(M);
	int blockSize = max(1, int(sqrt(N + 1)));
	for (int qi = 0; qi < M; ++qi) {
		int i, j; cin >> i >> j;
		// Work on prefix indices [i-1, j]
		qs[qi] = {i - 1, j, qi, (i - 1) / blockSize};
	}
	sort(qs.begin(), qs.end(), [&](const Query &a, const Query &b) {
		if (a.block != b.block) return a.block < b.block;
		if (a.block & 1) return a.R > b.R;
		return a.R < b.R;
	});

	// Data structures for Mo
	vector<deque<int>> positions(K); // positions of each compressed prefix value inside current window
	int lenBlock = max(1, int(sqrt(N + 1)));
	vector<int> cntLen(N + 1, 0); // how many values currently have span exactly d
	vector<int> bucket((N + lenBlock) / lenBlock + 2, 0); // number of d in block with cntLen[d] > 0

	auto incLen = [&](int d) {
		if (d < 0) return;
		if (++cntLen[d] == 1) bucket[d / lenBlock]++;
	};
	auto decLen = [&](int d) {
		if (d < 0) return;
		if (--cntLen[d] == 0) bucket[d / lenBlock]--;
	};
	auto spanOf = [&](const deque<int> &dq) -> int {
		if ((int)dq.size() < 2) return 0;
		return dq.back() - dq.front();
	};
	auto getMaxLen = [&]() -> int {
		for (int b = (int)bucket.size() - 1; b >= 0; --b) {
			if (bucket[b] == 0) continue;
			int start = min(N, (b + 1) * lenBlock - 1);
			int base = b * lenBlock;
			for (int d = start; d >= base; --d) {
				if (cntLen[d] > 0) return d;
			}
		}
		return 0;
	};

\tint curL = 0, curR = -1;
	vector<int> ans(M, 0);

	auto addLeft = [&](int idx) {
		int id = idOfIndex[idx];
		int oldSpan = positions[id].empty() ? -1 : spanOf(positions[id]);
		positions[id].push_front(idx);
		int newSpan = spanOf(positions[id]);
		if (oldSpan != -1) decLen(oldSpan);
		incLen(newSpan);
	};
	auto addRight = [&](int idx) {
		int id = idOfIndex[idx];
		int oldSpan = positions[id].empty() ? -1 : spanOf(positions[id]);
		positions[id].push_back(idx);
		int newSpan = spanOf(positions[id]);
		if (oldSpan != -1) decLen(oldSpan);
		incLen(newSpan);
	};
	auto removeLeft = [&](int idx) {
		int id = idOfIndex[idx];
		int oldSpan = spanOf(positions[id]); // must be present
		if (!positions[id].empty() && positions[id].front() == idx) positions[id].pop_front();
		int newSpan = positions[id].empty() ? -1 : spanOf(positions[id]);
		decLen(oldSpan);
		if (newSpan != -1) incLen(newSpan);
	};
	auto removeRight = [&](int idx) {
		int id = idOfIndex[idx];
		int oldSpan = spanOf(positions[id]);
		if (!positions[id].empty() && positions[id].back() == idx) positions[id].pop_back();
		int newSpan = positions[id].empty() ? -1 : spanOf(positions[id]);
		decLen(oldSpan);
		if (newSpan != -1) incLen(newSpan);
	};

	for (const auto &q : qs) {
		while (curL > q.L) addLeft(--curL);
		while (curR < q.R) addRight(++curR);
		while (curL < q.L) removeLeft(curL++);
		while (curR > q.R) removeRight(curR--);
		ans[q.idx] = getMaxLen();
	}

	for (int i = 0; i < M; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}