KLC 数点由 KLC 大神在模拟赛中发明。
其算法复杂度与答案值域大小挂钩。
其能解决的问题一般有着如下的特点：给定一个序列，每次询问一个区间有多少个子区间满足什么性质，数据随机生成。
其算法流程为：
-
通过某种方法预处理出所有满足性质的子区间
-
将得到的区间表示在二维平面上
-
将询问离线，转化为二维数点，使用扫描线解决
其答案依赖于期望分析。
例题：
给定一个长度为 \(n\) 的数列，每次询问区间 \([l, r]\) 中子区间是值域连续段的个数， \(q\) 次询问。数据随机生成（注：原题没有该性质，但是仍可过，为保证算法正确性，在这里放了修改版）
考虑 KLC 数点，期望分析容易得到长度为 \(2\) 的值域连续段约有 \(O (1)\) 个，长度增加时出现次数更少，长度为 \(1\) 的值域连续段显然有 \(n\) 个，那么总共约有 \(O (n)\) 个，总复杂度为 \(O ( log n)\).
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
int f[100010][30], g[100010][30], a[100010], ans[100010], n, q, l, r;
vector<array<int, 4> > v[100010];
struct BIT {
int tree[100010];
int lowbit(int x) { return x & (-x); }
void modify(int u, int d) {
while (u <= n) {
tree[u] += d;
u += lowbit(u);
}
}
int query(int u) {
int res = 0;
while (u) {
res += tree[u];
u -= lowbit(u);
}
return res;
}
}bit;
int findMin(int l, int r) {
int s = log2(r - l + 1);
return min(f[l][s], f[r - (1 << s) + 1][s]);
}
int findMax(int l, int r) {
int s = log2(r - l + 1);
return max(g[l][s], g[r - (1 << s) + 1][s]);
}
signed main() {
// freopen("cat.in", "r", stdin);
// freopen("cat.out", "w", stdout);
cin >> n;
rep (i, 1, n) {
cin >> a[i];
f[i][0] = a[i];
g[i][0] = a[i];
}
rep (j, 1, log2(n)) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
rep (i, 1, n) {
// v[i].push_back({0, i, 1, 0});
rep (j, i + 1, n) {
int mmin = findMin(i, j), mmax = findMax(i, j);
if (mmax - mmin + 1 == (j - i + 1)) {
v[i].push_back({0, j, 1, 0});
} else {
j = mmax - mmin + i - 1;
}
}
}
cin >> q;
rep (i, 1, q) {
cin >> l >> r;
v[l - 1].push_back({1, l, r, -i});
v[r].push_back({1, l, r, i});
ans[i] = r - l + 1;
}
rep (i, 1, n) {
for (auto j:v[i]) {
if (j[0]) {
int id = 0, val = 0;
if (j[3] > 0) id = j[3], val = 1;
else id = -j[3], val = -1;
// cout << id << " " << bit.query(j[2]) - bit.query(j[1] - 1) << "\n";
ans[id] += (bit.query(j[2]) - bit.query(j[1] - 1)) * val;
} else {
bit.modify(j[1], j[2]);
}
}
}
rep (i, 1, q) {
cout << ans[i] << "\n";
}
}