서론
이전에는 잘 이해하지 못해 문제를 풀 때마다 막혔지만, 최근 교육에서 이 개념을 다시 배우면서 깊이 이해하게 되어 이를 정리한 노트를 작성하게 되었습니다.
여기서 다루는 스캔라인은 더 정확히 말해 오프라인 2차원 수 문제를 의미하며, 한 차원은 스캔라인으로 관리하고 다른 차원은 자료구조로 관리하는 방식입니다.
개념
2차원 수 문제를 평면에 나타내면, 각 쿼리나 제약은 평면上的 사각형에 해당합니다. 이 사각형의 \(\text{side}\) 수는 제약된 경계의 수로 정의됩니다(좌표축이나 상한선은 제약으로 간주하지 않음).
기본 문제
백준 P10814 【템플릿】오프라인 2차원 수 문제
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(m\)개의 쿼리가 주어집니다. 각 쿼리는 \(l,r,x\)로 주어지며, \(\sum_{i=l}^r[a_i\leq x]\)를 구해야 합니다.
모든 데이터에 대해 \(1\leq n,m,a_i,l,r,x\leq 2\times 10^6\)입니다.
풀이
템플릿 문제입니다. \(i\)를 한 차원으로, \(a_i\)를 다른 차원으로 평면을 구성합니다. 그러면 각 쿼리는 \(l\leq i\leq r \land a_i\leq x\)인 \(\text{3-side}\) 사각형이 됩니다. 따라서 \(a_i\) 차원에 대해 스캔라인을 적용하여 \((i,a_i)\) 점을 \(a_i\)에 연결하고, \((l,r,x)\) 쿼리를 \(x\)에 연결합니다. 특정 \(x\)를 스캔할 때 해당 \(x\)에 연결된 모든 점 \((i,x)\)을 가져와 단점 업데이트를 수행한 후, \(x\)에 연결된 모든 쿼리 \((l,r,x)\)에 대한 답변을 제공합니다. 단점 업데이트와 구간 쿼리를 지원해야 하므로 선분 트리(BIT)를 사용합니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
물론 \(i\) 차원에 대해 스캔라인을 적용하고, 값 선분 트리를 사용하여 쿼리에 답변하는 방법도 있습니다. 이 방법이 더 일반적으로 사용됩니다.
구현 및 코드
구현 방법에 대해 설명하겠습니다. 스캔라인에는 일반적으로 두 가지 구현 방식이 있습니다. 하나는 스캔할 차원을 정렬한 후 이중 포인터를 이동하는 방식이고, 다른 하나는 스캔할 차원의 각 위치에 \(vector\)를 직접 열어, 업데이트나 쿼리 시 해당 위치에 연결된 점이나 쿼리를 직접 가져오는 방식입니다. 전자의 상수 요소가 후자보다 더 좋습니다.
여기서 첫 번째 방식의 구현을 제공합니다:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e6 + 5, M = 2e6 + 5, V = 2e6 + 5;
namespace FastIO {
const int S = 20 + 5;
int szb;
char buf[S];
int read() {
int s = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') s = -1;
int x = 0;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
return s * x;
}
void write(int x, char sep = '\n') {
if (x < 0) putchar('-'), x = -x;
do { buf[++szb] = x % 10 + '0', x /= 10; } while (x);
while (szb) putchar(buf[szb--]);
putchar(sep);
}
}
using namespace FastIO;
int n, m, sz, a[N], ans[M];
struct Query {
int id, x, v, tp;
bool operator<(const Query &q) const { return x < q.x; };
} q[M << 1];
struct BIT {
int c[V];
int query(int x) {
int s = 0;
for (; x; x -= lowbit(x)) s += c[x];
return s;
}
void add(int x, int v) { for (; x <= V - 5; x += lowbit(x)) c[x] += v; }
} ft;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
n = read(), m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= m; ++i) {
int l = read(), r = read(), v = read();
if (l > 1) q[++sz] = { i, l - 1, v, -1 };
q[++sz] = { i, r, v, 1 };
}
sort(q + 1, q + sz + 1);
for (int i = 1, j = 1; i <= n; ++i) {
ft.add(a[i], 1);
while (j <= sz && q[j].x <= i) ans[q[j].id] += ft.query(q[j].v) * q[j].tp, ++j;
}
for (int i = 1; i <= m; ++i) write(ans[i]);
return 0;
}
백준 P1972 [SDOI2009] HH의 목걸이
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(m\)개의 쿼리 \(l,r\)가 주어집니다. 구간의 색상 수를 구해야 합니다, 즉 구간 내에 있는 서로 다른 원소의 개수입니다.
모든 데이터에 대해 \(1\leq n,m,a_i\leq 10^6\)입니다.
풀이
매우 전형적인 문제입니다. 색상 수 관련 문제의 경우, 각 위치 \(i\) 앞에서 \(a_i\) 값과 처음으로 같은 위치 \(pre_i\)를 미리 처리하는 방식을 생각할 수 있습니다. 그러면 구간 쿼리에 대해 모든 첫 번째 등장 위치가 기여하게 하면, 총 기여도가 바로 색상 수가 됩니다. 구간 내의 특정 위치 \(i\)의 수가 첫 번째 등장하는 조건은 \(pre_i<l\)입니다. 따라서 \(i\)를 한 차원으로, \(pre_i\)를 다른 차원으로 평면을 구성하면, 각 쿼리는 \(\text{3-side}\) 사각형 내 점의 수를 쿼리하는 것과 같습니다. 이전 문제와 마찬가지로 두 가지 스캔 방식이 있으며, \(pre_i\)에 대해 스캔라인을 적용하거나, \(i\)에 대해 스캔라인을 적용하고 \(pre_i\)에 대해 값 선분 트리를 구축할 수 있습니다. 시간 복잡도는 여전히 \(O(n\log{n})\)입니다.
쿼리에 대한 평면 구성
구간 쿼리의 경우, 각각 \(q_l\)과 \(q_r\)을 좌표축으로 평면을 구성하는 것도 매우 전형적인 기술입니다. 구체적으로, 우리는 어떤 쿼리 \((l,r)\)이 답변에 기여하는지 생각해봅니다. "기여하는" 제약은 평면에서 특정 종류의 사각형으로 나타나며, 이는 평면의 사각형 추가/덮기 작업과 같이 변환됩니다. 쿼리는 단점 쿼리로 변환됩니다.
CodeForces 522D 가장 가까운 동일 요소
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(m\)개의 쿼리 \(l,r\)가 주어집니다. \(a[l,r]\)에서 거리가 가장 가까운 동일한 요소를 찾으세요. 거리는 인덱스 차이의 절댓값으로 정의됩니다.
모든 데이터에 대해 \(1\leq n,m\leq 5\times 10^5\)입니다.
풀이
전형적인 문제입니다. 모든 극히 가까운 동일한 요소의 위치 쌍 \((i,j)\)를 찾으면, \(l\leq i\land r\geq j\)인 경우, 해당 위치 쌍은 쿼리 구간에 \(j-i\)의 \(\operatorname{chkmin}\) 기여를 합니다. 문제는 \(\text{2-side}\) 사각형 \(\operatorname{chkmin}\)과 단점 쿼리로 변환됩니다. 임의의 한 차원에 대해 스캔라인을 적용할 수 있으며, 당연히 세그먼트 트리 Beats로 해결할 수 있습니다. 하지만 명백히 우리는 전/후缀 \(\operatorname{chkmin}\)을 수행하며, 이러한 특수한 최값 작업에 대해 더 간단한 구현 방식이 있습니다. \(\operatorname{chkmin}\) 작업의 경우, 특정 종류의 태그 방식을 사용하여 단점에서 직접 최값 수정을 수행하고, 단점 쿼리 시 전/후缀 \(\min\)을 쿼리하면 답이 됩니다. 선분 트리로 관리할 수 있습니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
UOJ #637 【메이투컵2021】A. 자료구조
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(m\)개의 쿼리 \(l,r\)가 주어집니다. \(a[l,r]\) 구간에 1을 더한 후의 전체 색상 수를 구하세요. 쿼리는 서로 독립적입니다.
모든 데이터에 대해 \(1\leq a_i\leq n\), \(1\leq n,m\leq 10^6\)입니다.
풀이
상당히 흥미로운 문제입니다. 정이역반을 생각해보고, 각 색상 \(x\)에 대해 어떤 쿼리 구간 \((l,r)\)이 그 기여를 제거하는지 고려합니다. 간단한 분석을 통해 다음 두 조건을 동시에 만족해야 함을 알 수 있습니다:
- 모든 \(x\)가 1씩 증가합니다;
- 모든 \(x-1\)이 1씩 증가하지 않습니다.
첫 번째 조건에 대해, \(x\)의 첫 번째/마지막 출현 위치 \(st_x/ed_x\)를 미리 처리하면, \(l\leq st_x \land r\geq ed_x\)가 됩니다. 두 번째 조건에 대해, \(x-1\)의 모든 극히 가까운 위치 쌍 \(i,j\)를 고려하면, 각 위치 쌍은 제약 \(l\geq i+1\land r\leq j-1\)입니다. 이러한 모든 제약의 합집합이 두 번째 조건의 제약이 됩니다. 최종 제약은 두 가지 제약의 교집합이며, 평면에서 고려하면, 첫 번째 제약은 \(\text{2-side}\) 사각형이고, 두 번째 제약은 일련의 점들이 연결된 사각형입니다. 교집합은 \(x-1\)의 출현 위치 시퀀스 \(pos_{x-1}\)에서 \(st_x\)의 전구체 \(prv\)와 \(ed_x\)의 후속자 \(nxt\)를 찾아, \(prv+1\leq l\leq st_x\land ed_x\leq r\leq nxt-1\)인 \(\text{4-side}\) 사각형 교집합을 얻습니다.
문제는 여러 개의 \(\text{4-side}\) 사각형 추가(물론 \(\text{2-side}\)도 있으며, 가장 강력한 제약을 선택)와 단점 쿼리로 변환됩니다. 이는 매우 전형적인 문제로, 임의의 한 차원에 대해 스캔라인을 적용하고, 차분하여 업데이트 값이 입경을 스캔할 때 기여를 하고, 출경을 스캔한 후 기여를 제거하면, 이는 시퀀스의 구간 추가와 단점 쿼리로 변환되며, 선분 트리로 차분 배열을 관리할 수 있습니다.
코드
일부 논의가 필요하므로 주요 부분을 제공합니다. 코드가 비교적 오래되어서 쓰여서 \(vector\) 구현 버전을 작성했습니다.
void addr(int lmn, int lmx, int rmn, int rmx) {
ops[lmn].push_back({ rmn, rmx, 1 });
ops[lmx + 1].push_back({ rmn, rmx, -1 });
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1, l, r; i <= m; ++i) cin >> l >> r, qr[l].push_back({ i, r });
for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
cnt = n + 1;
for (int i = 1; i <= n + 1; ++i) {
int lmn = 1, lmx = INF, rmn = -INF, rmx = n;
if (pos[i].empty()) {
if (!pos[i - 1].empty()) {
addr(1, pos[i - 1].front() - 1, 1, pos[i - 1].front() - 1);
addr(pos[i - 1].back() + 1, n, pos[i - 1].back() + 1, n);
for (int j = 0; j < pos[i - 1].size() - 1; ++j) {
int l = pos[i - 1][j], r = pos[i - 1][j + 1];
addr(l + 1, r - 1, l + 1, r - 1);
}
} else --cnt;
continue;
}
int st = pos[i].front(), ed = pos[i].back();
int l = 1, r = n;
bool suc = true;
for (int &p : pos[i - 1]) {
if (st <= p && p <= ed) { suc = false; break; }
if (p < st) l = max(l, p + 1);
if (p > ed) r = min(r, p - 1);
}
if (suc) addr(l, st, ed, r);
}
for (int i = 1; i <= n; ++i) {
for (Op &op : ops[i]) {
int l = op.l, r = op.r, v = op.v;
ft.add(l, v); ft.add(r + 1, -v);
}
for (Query &q : qr[i]) ans[q.id] = ft.query(q.x);
}
for (int i = 1; i <= m; ++i) cout << cnt - ans[i] << '\n';
return 0;
}
구간 오른쪽 끝점 스캔라인
또 다른 기술은 구간의 오른쪽 끝점을 스캔라인으로 사용하여, 모든 왼쪽 끝점부터 현재 오른쪽 끝점까지의 답변을 자료구조로 관리하는 것입니다. 구간 왼쪽 끝점을 역순으로 스캔하는 것도 가능합니다.
QOJ #8672 줄서기
문제
\(n\)개의 구간 \([l_i,r_i]\)가 주어집니다. \(f_i(x)=x+[x\in[l_i,r_i]]\로 정의합니다. \(q\)번의 쿼리 \(L,R\)에 대해, \(f_R(f_{R-1}\cdots f_L(0)))\)를 구하세요.
모든 데이터에 대해 \(1\leq n,q\leq 10^6\)입니다.
풀이
이것은 우리의 ABC389F가 아닙니까?
오른쪽 끝점에 대해 스캔라인을 적용하고, 모든 \(a_L=f_R(f_{R-1}\cdots f_L(0)))\)의 값을 관리합니다. \(R\leftarrow R+1\)일 때 \(a\)가 어떻게 변하는지 고려해봅시다. 명백히 \(a_L\in[l_R,r_R]\이면, \(a_L\leftarrow a_L+1\)입니다. 그리고 \(a_L\)은 \(L\)에 대해 단조 감소함을 알 수 있으므로, 변화가 발생하는 위치는 연속적이며, 이를 이분 탐색으로 찾을 수 있습니다. 따라서 구간 추가와 단점 쿼리를 지원해야 하며, 선분 트리에서 이분 탐색이나 선분 트리에서 배증을 사용하여 \(O(n\log{n})\)으로 해결할 수 있습니다. 하지만 이 문제는 이중 로그를 따지지 않습니다.
CodeForces 793F Julia the snail
문제
길이가 \(n\)의 막대기가 있고, 그 위에 \(m\)개의 줄이 있습니다. 각 줄은 달팽이가 \(l_i\)에서 \(r_i\)까지 기어갈 수 있게 합니다(중간에 떨어질 수 없습니다). 달팽이는 자연히 떨어질 수도 있습니다. \(q\)번의 쿼리 \(x,y\)에 대해, 높이 \(x\)에서 출발하여, 여정 중 높이가 \(x\) 이하이거나 \(y\) 이상이 되지 않을 때, 최대로 도달할 수 있는 높이를 구해야 합니다.
모든 데이터에 대해 \(1\leq n,m,q\leq 10^5\)이며, \(r_i\)가 서로 다름이 보장됩니다.
풀이
이 엉망진창 문제도 3000점인가요?
여전히 오른쪽 끝점 \(R\)에 대해 스캔라인을 적용하고, 모든 \(f_L\)을 높이 제한이 \([L,R]\) 내일 때 도달할 수 있는 최대 높이로 관리합니다. \(R\rightarrow R+1\)일 때, \(R\)을 오른쪽 끝으로 하는 줄 \([L',R]\을 고려합니다. 그러면 모든 \(f_L\geq L'\)에 대해, 명백히 달팽이가 \(f_L\)에서 자연히 미끄러져 \(L'\)로 내려간 후 \(R\)까지 기어 올라갈 수 있으므로, 이때 \(f_L\leftarrow R\)로 설정합니다. Segment Tree Beats를 사용하여 \(O(n\log{n})\)으로 해결할 수 있습니다.
CodeForces 1083D The Fair Nut's getting crazy
문제
길이가 \(n\)인 수열 \(a\)가 주어집니다. 이 수열에서 두 개의 비어 있지 않은 부분 구간을 선택해야 합니다:
- 두 부분 구간은 포함 관계가 아니어야 합니다;
- 두 부분 구간은 교집합을 가지며, 교집합에 있는 각 요소는 각 부분 구간에서 한 번만 나타나야 합니다.
총 몇 가지 다른 부분 구간 선택 방법이 있는지 구하세요. 결과를 \(10^9 + 7\)로 모듈러한 값을 출력하세요.
부분 구간 \([a, b],[c, d]\를 선택하는 것과 \([c, d],[a, b]\를 선택하는 것은 서로 다른 두 가지 방법으로 간주됩니다.
모든 데이터에 대해 \(1\leq n\leq 10^5, -10^9\leq a_i\leq 10^9\)입니다.
풀이
\(a<c\leq b<d\)라고 가정합시다. 매우 단순한 생각은 교집합 구간 \([c,b]\를 열거하고, 각 위치 \(i\) 앞/뒤에서 \(a_i\) 값과 처음으로 같은 위치 \(pre_i/nxt_i\)를 미리 처리하는 것입니다. 우리는 \(a\geq\max_{i=c}^b\{pre_i\}+1\)와 \(d\leq \min_{i=c}^b\{nxt_i\}-1\)를 가집니다. 따라서 이때 선택할 수 있는 부분 구간의 수는 \(((c-1)-mx)(mn-(b+1))\)입니다.
스캔라인으로 최적화합니다. \(R\)에 대해 스캔라인을 적용하고, 각 \(L\)에 대해 교집합 구간이 \([L,R]\일 때의 부분 구간 수를 관리한 후, 선분 트리로 구간 합을 누적하여 답에 더합니다. 다음을 관리해야 합니다:
[\begin{align*} &\sum ((L-1)-mx)(mn-(R+1)) \ =&\sum (L-1)mn-(L-1)(R+1)-mx\times mn+(R+1)mx \ =&\sum (L-1)mn-(R+1)\sum(L-1)-\sum mx\times mn+(R+1)\sum mx \end{align*} ]따라서 선분 트리의 각 노드에서 \(\sum (L-1)mn,\sum mx,\sum mn,\sum mx\times mn\)을 관리해야 합니다.
\(R\leftarrow R+1\) 후 \(mn\)과 \(mx\)가 변화하며, 이러한 변화에 대한 전형적인 패턴이 있습니다. 후缀 최값을 관리해야 함을 고려하고, \(mx\)를 예로 들어, 우리는 단조 스택을 유지합니다. \(a_R\)을 추가할 때, \(mx\)는 성 단위로 변화합니다. 구체적으로, 스택 내 요소가 단조 감소하는 스택을 유지하고, 스택 상단을 \(top\)이라고 하면, 실제로 이는 후缀 최값 정보를 함축합니다:
[\max_{i=stk_{top-1}+1}^{stk_{top}}=a_{stk_{top}} ]\(a_{stk_{top}}\leq a_R\일 때, 스택 상단을 팝하고 동시에 이 구간의 \(mx\leftarrow a_R\로 업데이트하면, \(mx\)를 올바르게 관리할 수 있으며, \(mn\)도 마찬가지입니다. 스택 상단을 팝할 때만 \(1\)번의 구간 커버를 수행하므로, 구간 커버의 총 횟수는 \(O(n)\)입니다.
스캔라인 과정에서 동시에 중복 요소가 없는 교집합 구간의 최대 길이를 이중 포인터로 구하고, 선분 트리와 단조 스택을 조합하여 해결합니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
코드
코드 작성이 어렵기 때문에 주요 부분을 제공합니다.
struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
struct Node { ll sum[4], tg[2]; } nodes[(N << 2) + 5];
void push_up(int p) {
for (int i = 0; i < 4; ++i)
nodes[p].sum[i] = (nodes[ls(p)].sum[i] + nodes[rs(p)].sum[i]) % MOD;
}
void make_change(int p, int l, int r, ll v, int tp) {
nodes[p].sum[2] = nodes[p].sum[tp ^ 1] * v % MOD;
nodes[p].sum[tp] = v * (r - l + 1) % MOD;
if (!tp) nodes[p].sum[3] = v * (1ll * (l + r) * (r - l + 1) / 2 % MOD) % MOD;
nodes[p].tg[tp] = v;
}
void push_down(int p, int l, int r) {
int mid = (l + r) >> 1;
for (int i = 0; i <= 1; ++i) {
if (!nodes[p].tg[i]) continue;
make_change(ls(p), l, mid, nodes[p].tg[i], i),
make_change(rs(p), mid + 1, r, nodes[p].tg[i], i);
nodes[p].tg[i] = 0;
}
}
ll query(int p, int l, int r, int x, int y, int tp) {
if (x <= l && y >= r) return nodes[p].sum[tp];
push_down(p, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if (x <= mid) res = query(ls(p), l, mid, x, y, tp);
if (y > mid) res = (res + query(rs(p), mid + 1, r, x, y, tp)) % MOD;
return res;
}
void change(int p, int l, int r, int x, int y, ll v, int tp) {
if (x <= l && y >= r) { make_change(p, l, r, v, tp); return; }
push_down(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) change(ls(p), l, mid, x, y, v, tp);
if (y > mid) change(rs(p), mid + 1, r, x, y, v, tp);
push_up(p);
}
#undef ls
#undef rs
} sgt;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], da[++sz] = a[i];
sort(da + 1, da + sz + 1); sz = unique(da + 1, da + sz + 1) - (da + 1);
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(da + 1, da + sz + 1, a[i]) - da;
pre[i] = pos[a[i]] + 1; pos[a[i]] = i;
}
for (int i = 1; i <= sz; ++i) pos[i] = n + 1;
for (int i = n; i; --i) nxt[i] = pos[a[i]] - 1, pos[a[i]] = i;
for (int i = n; i; --i) {
while (top && pre[stk[top]] < pre[i]) --top;
fp[i] = top ? stk[top] : n + 1; stk[++top] = i;
}
top = 0;
for (int i = n; i; --i) {
while (top && nxt[stk[top]] > nxt[i]) --top;
fn[i] = top ? stk[top] : n + 1; stk[++top] = i;
}
for (int l = n, r = n; l; --l) {
if (l < fp[l]) sgt.change(1, 1, n, l, fp[l] - 1, pre[l], 0);
if (l < fn[l]) sgt.change(1, 1, n, l, fn[l] - 1, nxt[l], 1);
++cnt[a[l]];
while (cnt[a[l]] > 1) --cnt[a[r--]];
ans = (ans + sgt.query(1, 1, n, l, r, 1) * l % MOD) % MOD;
ans = (ans + sgt.query(1, 1, n, l, r, 3)) % MOD;
ans = (ans - sgt.query(1, 1, n, l, r, 2)) % MOD;
ans = (ans - 1ll * l * (1ll * (l + r) * (r - l + 1) / 2 % MOD)) % MOD;
}
cout << (ans + MOD) % MOD;
return 0;
}
구간 부분 구간 문제
또 다른 종류의 문제는 여러 번 구간을 쿼리하여, 이 구간 내 모든 부분 구간의 기여도 누적값을 구하는 것입니다.
먼저 우리의 【템플릿】선분 트리 3, 즉 구간 역사 최값/버전 합을 할 줄 알아야 합니다. 우리는 여전히 \(R\)에 대해 스캔라인을 적용합니다. 그러면 쿼리 \([L,R]\에 대해, \([L,R]\의 구간 합을 쿼리하면, 이는 구간 내 모든 \(R\)을 오른쪽 끝점으로 하는 부분 구간의 기여도 합과 같습니다. 하지만 \([L,R]\의 구간 역사 버전 합을 쿼리하면 어떻게 될까요? 실제로 이는 구간 내 모든 부분 구간의 기여도 합을 쿼리하는 것과 같습니다.
위 그림과 같이, 우리가 구해야 하는 것은 파란색 영역 내의 기여도 합입니다. 구간 역사 버전 합을 쿼리하는 것은 실제로 파란색 경계 내의 \(\text{3-side}\) 사각형 내 기여도 합을 쿼리하는 것과 같지만, 이는 여전히 올바릅니다. \(L\leq R\)임을 주의하면, 모든 구간 표현 점이 \(L=R\) 직선 아래에 위치하므로, 우리가 추가로 쿼리한 부분에는 유효한 구간이 없습니다.
백준 P3246 [HNOI2016] 시퀀스
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(q\)번의 쿼리 \(l,r\)에 대해, \(a[l,r]\) 내 모든 부분 구간의 최소값 합을 구하세요.
모든 데이터에 대해 \(1\leq n,q\leq 10^5\)입니다.
풀이
농룡 문제입니다. \(r\)에 대해 스캔라인을 적용하고, 앞의 단조 스택 기술을 사용하여 모든 \(\min_{i=l}^r\{a_i\}\)을 관리합니다. 그러면 간단한 구간 추가와 구간 역사 버전 합 문제입니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
CodeForces 997E Good Subsegments
문제
길이가 \(n\)인 순열 \(p\)가 주어집니다. 구간 \([l,r]\가 좋다는 것은 \(p[l,r]\가 값역에서 연속적일 때를 의미합니다. \(q\)번의 쿼리 \(l,r\에 대해, \(a[l,r]\에서 몇 개의 부분 구간이 좋은지 구하세요.
모든 데이터에 대해 \(1\leq n,q\leq 1.2\times 10^5\)입니다.
풀이
순열이므로, 구간이 좋다는 것은 \(mx-mn+1=r-l+1\)와 동일합니다. 따라서 스캔라인 과정에서 \(mx-mn+l\)을 관리하고, \(mx-mn+l\ge r\)임을 관찰합니다. 따라서 최소값과 출현 횟수를 기록하고, 출현 횟수의 역사 버전 합을 관리하면 됩니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
코드
주로 선분 트리 부분을 제공합니다.
이중 경험
struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
struct Node { ll mn, cmn, hcmn, tg_add, tg_cnt; } nodes[N << 2];
void push_up(int p) {
nodes[p].mn = min(nodes[ls(p)].mn, nodes[rs(p)].mn);
nodes[p].cmn = 0;
if (nodes[ls(p)].mn == nodes[p].mn) nodes[p].cmn += nodes[ls(p)].cmn;
if (nodes[rs(p)].mn == nodes[p].mn) nodes[p].cmn += nodes[rs(p)].cmn;
}
void make_add(int p, ll add, ll cnt) {
nodes[p].mn += add; nodes[p].tg_add += add;
nodes[p].tg_cnt += cnt; nodes[p].hcmn += cnt * nodes[p].cmn;
}
void push_down(int p) {
ll &add = nodes[p].tg_add, &cnt = nodes[p].tg_cnt;
ll mn = min(nodes[ls(p)].mn, nodes[rs(p)].mn);
make_add(ls(p), add, nodes[ls(p)].mn == mn ? cnt : 0);
make_add(rs(p), add, nodes[rs(p)].mn == mn ? cnt : 0);
add = cnt = 0;
}
void build(int p, int l, int r) {
nodes[p].tg_add = nodes[p].tg_cnt = 0;
nodes[p].mn = l; nodes[p].cmn = 1;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
push_up(p);
}
void add(int p, int l, int r, int x, int y, ll v) {
if (x <= l && y >= r) { make_add(p, v, 0); return; }
push_down(p);
int mid = (l + r) >> 1;
if (x <= mid) add(ls(p), l, mid, x, y, v);
if (y > mid) add(rs(p), mid + 1, r, x, y, v);
push_up(p);
}
ll query(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) return nodes[p].hcmn;
push_down(p);
int mid = (l + r) >> 1; ll res = 0;
if (x <= mid) res = query(ls(p), l, mid, x, y);
if (y > mid) res += query(rs(p), mid + 1, r, x, y);
return res;
}
#undef ls
#undef rs
} sgt;
백준 P10822 [EC Final 2020] Prof. Pang's sequence
문제
길이가 \(n\)인 수열 \(a\)가 주어지고, \(m\)번의 쿼리 \(l,r\에 대해, \(a[l,r]\에서 색상 수가 홀수인 부분 구간의 개수를 구하세요.
모든 데이터에 대해 \(1\leq n,m\leq 5\times 10^5\)입니다.
풀이
부분 구간의 색상 수가 홀수인 개수는 모든 부분 구간의 색상 수 \(\bmod 2\)의 합과 동일함을 주목합니다. 스캔라인으로 부분 구간 색상 수 \(\bmod 2\)를 관리하면, \(0/1\) 시퀀스를 관리하는 것과 같습니다. \(R\leftarrow R+1\)일 때, \([pre_R+1,R]\의 색상 수가 모두 \(+1\)이므로, \(0/1\) 시퀀스에서는 구간 반전을 의미합니다. 따라서 구간 반전과 역사 버전 합을 지원해야 하며, \(rev\) 태그가 적용된 상태와 적용되지 않은 상태에 대해 각각 역사 버전 합의 업데이트 표시의 개수를 기록하면 됩니다. 시간 복잡도는 \(O(n\log{n})\)입니다.
코드
여전히 선분 트리 코드를 제공합니다.
struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
struct Node { ll sum, hsum, cnt0, cnt1, tg; } nodes[N << 2];
void push_up(int p) {
nodes[p].sum = nodes[ls(p)].sum + nodes[rs(p)].sum;
nodes[p].hsum = nodes[ls(p)].hsum + nodes[rs(p)].hsum;
}
void make_tg(int p, int l, int r, int cnt0, int cnt1, int tg) {
nodes[p].hsum += nodes[p].sum * cnt0 + (r - l + 1 - nodes[p].sum) * cnt1;
if (nodes[p].tg) nodes[p].cnt0 += cnt1, nodes[p].cnt1 += cnt0;
else nodes[p].cnt0 += cnt0, nodes[p].cnt1 += cnt1;
if (tg) nodes[p].tg ^= 1, nodes[p].sum = r - l + 1 - nodes[p].sum;
}
void push_down(int p, int l, int r) {
int mid = (l + r) >> 1;
make_tg(ls(p), l, mid, nodes[p].cnt0, nodes[p].cnt1, nodes[p].tg);
make_tg(rs(p), mid + 1, r, nodes[p].cnt0, nodes[p].cnt1, nodes[p].tg);
nodes[p].cnt0 = nodes[p].cnt1 = nodes[p].tg = 0;
}
void build(int p, int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
push_up(p);
}
ll query(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) return nodes[p].hsum;
push_down(p, l, r);
int mid = (l + r) >> 1; ll res = 0;
if (x <= mid) res = query(ls(p), l, mid, x, y);
if (y > mid) res += query(rs(p), mid + 1, r, x, y);
return res;
}
void rev(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) { make_tg(p, l, r, 0, 0, 1); return; }
push_down(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) rev(ls(p), l, mid, x, y);
if (y > mid) rev(rs(p), mid + 1, r, x, y);
push_up(p);
}
#undef ls
#undef rs
} sgt;
차원 변환 스캔라인
매우 일반적인 자료구조 문제의 경우, 우리는 일반적으로 시간 순서대로 작업을 수행합니다. 시퀀스 한 차원과 시간 한 차원으로 평면을 구성하면, 이는 시간 차원에 대해 스캔라인을 수행하는 것과 같습니다. 더 복잡한 작업의 경우, 이 방식이 다소 부적절할 수 있으므로, 시퀀스 차원에 대해 스캔라인을 적용할 수 있을까요? 답은 긍정적입니다. 이러한 방식을 차원 변환 스캔라인이라고 합니다. 단점 쿼리와 수정 작업이 차분 가능한 경우, 차원 변환 스캔라인을 고려할 수 있습니다.
백준 P3863 시퀀스
문제
길이가 \(n\)인 시퀀스와 \(q\)개의 작업이 주어집니다:
1 l r x: 시퀀스 인덱스가 \([l,r]\인 요소에 \(x\)를 더합니다;2 p y: \(a_p\)가 과거의 몇 초 동안 \(\geq y\)였는지 쿼리합니다 (이 초는 포함하지 않음).
시작 시점은 0초이며, \(i\)번째 작업은 \(i\)초에 발생합니다.
모든 데이터에 대해 \(2 \leq n,q \leq 10^5\), \(-10^9 \leq x,y,a_i \leq 10^9\)입니다.
풀이
매우 명백한 차원 변환 스캔라인입니다. 작업 \(2\)는 시간과 관련된 쿼리이므로, 차원 변환 스캔라인을 고려하도록 유도합니다. 작업 \(1\)을 \(a_l\)에 \(x\)를 더하고, \(a_{r+1}\)에 \(x\)를 빼는 방식으로 차분합니다. 시퀀스 차원에 대해 스캔라인을 적용하고, 자료구조로 시간 축 정보를 관리하면, 작업 \(2\)는 시간점 \(p\) 이전에 몇 개의 시점에 해당하는 접두합 \(\geq y\)인지 쿼리하는 것과 같습니다. 접두합 시퀀스를 직접 관리하는 것을 고려해봅시다. 그러면 문제는 후缀 추가와 특정 접두에 몇 개의 수 \(\geq y\)인지 쿼리로 변환됩니다. 이는 고전적인 분할 블록으로 해결할 수 있는 문제입니다. 시퀀스를 분할하여, 각 정수 블록은 추가 표시와 정렬된 \(vector\)를 저장합니다. 후缀 추가 시, 정수 블록은 직접 표시에 해당 값을 더하고, 분할 블록은 추가하고 해당 정수 블록을 재구축합니다. 쿼리 시, 정수 블록의 \(vector\)를 이분 탐색하고, 분할 블록은 여전히 누적 답변을 계산합니다.
블록 길이를 \(t\)라고 하면, 시간 복잡도는 \(O(q\log{q}+q(\frac{q}{t}+t\log{t})+q(\frac{q}{t}\log{t}+t))\)입니다. \(t=\sqrt{q}\)를 선택하면 \(O(q\sqrt{q}\log{q})\)입니다. 하지만 실제로 \(t=\sqrt{\frac{q}{\log{q}}}를 선택하면 더 나은 효율을 얻을 수 있으며, 이는 대략 \(O(q\sqrt{q\log{q}})\)입니다.
백준 P7560 [JOISC 2021 Day1] フードコート
문제
\(n\개의 큐가 있습니다. 값역 \(m\)이 주어지고, \(q\�의 작업이 있습니다. 작업은 다음 세 가지입니다:
- \([l,r]\인 큐의 끝에 \(k\�개의 \(c\)를 추가합니다;
- \([l,r]\인 큐의 앞 \(k\�개의 수를 제거합니다. 크기가 \(k\�개보다 작으면 큐를 비웁니다;
- \(a\�번 큐에서 앞에서부터 \(b\�번째 수를 쿼리합니다. 크기가 \(b\�개보다 작으면 0을 반환합니다.
모든 데이터에 대해 \(1\leq c\leq m\�, \(1\leq n,m,q\leq 2.5\times 10^5\)입니다.
풀이
이 작업은 관리하기 어려워 보이지만, 명백한 단점 쿼리와 수정 작업이 차분 가능하므로, 차원 변환 스캔라인을 고려합니다. 이 문제에서는 큐 번호에 대해 스캔라인을 적용하고, 자료구조로 시간 축 정보를 관리합니다. 작업 \(1,2\)를 차분하여, \(L\�에서 \(k\�의 기여를 하고, \(R+1\�에서 기여를 제거합니다.
먼저 작업 \(2\�가 없을 때 어떻게 하는지 생각해봅시다. 명백히 시간 축에서 최소 접두합 \(\ge b\�인 위치를 이분 탐색하여, 해당 삽입된 수가 답이 됩니다. 그러면 작업 \(2\�가 추가된 후, 이 방법을 왜 사용할 수 없을까요? 삭제 작업은 접두합의 단조성을 파괴하여 이분 탐색으로 답을 찾을 수 없게 만듭니다.
약화하여 생각해봅시다. 이 빈 큐는 \(0\�에 대해 \(\max\�를 취하는 것이 번거롭습니다. 접두합이 항상 \(\ge 0\�인 경우를 생각해봅시다. 명백히, 이때 모든 삭제 작업을 연기해도 정확성에 영향을 주지 않습니다. 따라서 현재 쿼리 작업 전 작업 \(2\�의 기여 합과 \(\sum{del}\)을 기록하고, 오직 작업 \(1\�만 고려하는 작업 시퀀스에서 접두합 \(\ge b+\sum{del}\�인 최소 위치를 이분 탐색하면 답이 됩니다.
마지막으로 접두합이 바닥에 닿을 수 있음(<0)의 경우로 돌아갑니다. 이때 현재 쿼리 전 마지막 바닥에 닿은 시점을 고려합니다. 이 시점 이후에는 위의 방법을 적용하면 정확합니다!
주요 관찰: 마지막 바닥에 닿은 시점은 접두합이 최소인 시점입니다.
증명: 시점 \(i\�에서 바닥에 닌 후 시점 \(j\�에서 다시 바닥에 닌다는 것은 \(sum_j-sum_i<0\)와 동일함을 명백히 알 수 있습니다.
이제 어떤 작업을 지원해야 하는지 생각해봅시다. 먼저 \([1,b)\�의 접두합 최소값을 쿼리해야 함을 알 수 있습니다. 수정 작업은 이미 차원 변환 스캔라인으로 단점 추가 작업으로 변환되었으므로, 접두합 시퀀스를 관리하고, 쿼리 시 \([1,b)\�의 접두 최소값을 쿼리하며, 단점 추가는 후缀 추가로 변환합니다. 접두 최소값의 위치 \(p\�를 찾은 후, 오직 작업 \(1\�만 고려하는 작업 시퀀스의 \((p,t]\� 구간에서, 이분 탐색하여 접두합 \(\ge b+\sum{del}\�인 최소 위치를 찾아야 합니다. 여기서 \(t\�는 현재 쿼리의 시간입니다. 우리는 선분 트리로 기여 합 \(\sum{sum}\�와 오직 작업 \(1\�만 고려하는 기여 합 \(\sum{add}\)를 관리합니다. 이때 \(\sum{del}=\sum{add}-\sum{sum}\이고, 쿼리 시 선분 트리 이분 탐색을 수행하면 됩니다.
따라서 두 개의 선분 트리로 모든 필요한 정보를 관리할 수 있습니다. 시간 복잡도는 \(O(q\log{q})\)입니다.
코드
구현 시 일부 특별한 경우를 주의해야 합니다. 두 개의 선분 트리를 하나로 합쳤습니다.
이중 경험
#include <iostream>
#include <algorithm>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int Q = 5e5 + 5;
int n, m, q, num[Q];
ll ans[Q];
int cnt_qr, cnt_ops;
struct Query {
ll num, id, a, b;
bool operator<(const Query &x) const { return a < x.a; }
} qr[Q];
struct Op {
ll id, tp, a, k;
bool operator<(const Op &x) const { return a < x.a; }
} ops[Q];
struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
struct Node { ll sum, add_sum, mn, amn, tg; } nodes[Q << 2];
void push_up(Node &p, Node &lp, Node &rp) {
p.sum = lp.sum + rp.sum; p.add_sum = lp.add_sum + rp.add_sum;
p.mn = min(lp.mn, rp.mn);
p.amn = rp.mn <= lp.mn ? rp.amn : lp.amn;
}
void push_up(int p) { push_up(nodes[p], nodes[ls(p)], nodes[rs(p)]); }
void make_add(int p, int l, int r, ll v) { nodes[p].tg += v; nodes[p].mn += v; }
void push_down(int p, int l, int r) {
if (!nodes[p].tg) return;
int mid = (l + r) >> 1;
make_add(ls(p), l, mid, nodes[p].tg); make_add(rs(p), mid + 1, r, nodes[p].tg);
nodes[p].tg = 0;
}
void build(int p, int l, int r) {
if (l == r) { nodes[p].amn = l; return; }
int mid = (l + r) >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
push_up(p);
}
Node query(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) return nodes[p];
push_down(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid && y > mid) {
Node lres = query(ls(p), l, mid, x, y);
Node rres = query(rs(p), mid + 1, r, x, y), res;
return push_up(res, lres, rres), res;
}
return x <= mid ? query(ls(p), l, mid, x, y) : query(rs(p), mid + 1, r, x, y);
}
int find(int p, int l, int r, int x, ll &v) {
if (r < x) return 0;
push_down(p, l, r);
if (x <= l) {
if (nodes[p].add_sum < v) { v -= nodes[p].add_sum; return 0; }
if (l == r) return l;
}
int mid = (l + r) >> 1;
int res = find(ls(p), l, mid, x, v);
return res ? res : find(rs(p), mid + 1, r, x, v);
}
void add(int p, int l, int r, int x, int y, ll v) {
if (x <= l && y >= r) { make_add(p, l, r, v); return; }
push_down(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) add(ls(p), l, mid, x, y, v);
if (y > mid) add(rs(p), mid + 1, r, x, y, v);
push_up(p);
}
void add2(int p, int l, int r, int x, ll v, int tp) {
if (l == r) {
nodes[p].sum += v;
if (tp) nodes[p].add_sum += v;
return;
}
push_down(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) add2(ls(p), l, mid, x, v, tp);
else add2(rs(p), mid + 1, r, x, v, tp);
push_up(p);
}
#undef ls
#undef rs
} sgt;
using Node = SegTree::Node;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1, tp; i <= q; ++i) {
cin >> tp;
if (tp == 1) {
ll l, r, k; cin >> l >> r >> num[i] >> k;
ops[++cnt_ops] = { i, 1, l, k }; ops[++cnt_ops] = { i, 1, r + 1, -k };
} else if (tp == 2) {
ll l, r, k; cin >> l >> r >> k;
ops[++cnt_ops] = { i, 0, l, -k }; ops[++cnt_ops] = { i, 0, r + 1, k };
} else {
ll a, b; cin >> a >> b; ++cnt_qr;
qr[cnt_qr] = { cnt_qr, i, a, b };
}
ans[i] = m + 1;
}
sort(ops + 1, ops + cnt_ops + 1); sort(qr + 1, qr + cnt_qr + 1);
sgt.build(1, 1, q);
for (int i = 1, j = 1, k = 1; i <= n; ++i) {
while (j <= cnt_ops && ops[j].a == i)
sgt.add(1, 1, q, ops[j].id, q, ops[j].k),
sgt.add2(1, 1, q, ops[j].id, ops[j].k, ops[j].tp), ++j;
while (k <= cnt_qr && qr[k].a == i) {
if (qr[k].id == 1) { ans[qr[k++].num] = 0; continue; }
Node res = sgt.query(1, 1, q, 1, qr[k].id - 1);
int p = res.mn >= 0 ? 0 : res.amn;
Node res2 = sgt.query(1, 1, q, p + 1, qr[k].id);
ll del = res2.add_sum - res2.sum, val = qr[k].b + del;
int pos = sgt.find(1, 1, q, p + 1, val);
ans[qr[k].num] = (!pos || pos > qr[k].id) ? 0 : num[pos];
++k;
}
}
for (int i = 1; i <= cnt_qr; ++i) cout << ans[i] << '\n';
return 0;
}