P1972 SDOI2009 HH的项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
维护一个长度同为 \(n\) 的数组 \(b\)。一个指针 \(R\) 从 \(1\) 扫到 \(n\) 并做如下操作：
- 检查是否有 \(k <R\) 满足 \(a_k = a_R\)。若有，将 \(b_k\) 设为 \(0\)。
- 将 \(b_R\) 设为 \(1\)；
- 回答所有右端点为 \(R\) 的询问 \([L, R]\)，答案就是 \(b\) 在 \([L, R]\) 上的区间和。
举例：\((1, 2, 1, 2, 1, 3)\)。\(R\) 分别为 \(1, 2, 3, 4, 5, 6\) 时，\(b\) 数组的变化：
- \(R = 1\)，\((1, 0, 0, 0, 0, 0)\)；
- \(R = 2\)，\((1, 1, 0, 0, 0, 0)\)；
- \(R=3\)，\((0, 1, 1, 0, 0, 0)\)，此时回答 \([1, 3]\) 时 \(b_1 = 0\)，相当于不再统计 \(a_1\)（因为已与 \(a_3\) 重复）；
- \(R = 4\)，\((0, 0, 1, 1, 0, 0)\)；
- \(R = 5\)，\((0, 0, 0, 1, 1, 0)\)；
- \(R = 6\)，\((0,0, 0, 1, 1, 1)\)；
对 \(b\) 使用树状数组加速。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-20 17:43:24
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-20 18:10:01
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
inline int lowbit(int x) {
return x & (-x);
}
const int maxn = (int)1e6 + 5;
const int maxq = (int)1e6 + 5;
const int maxv = (int)1e6 + 5;
int a[maxn], lst[maxv], c[maxn];
int n;
inline void add(int x, int v) {
for (; x <= n; x += lowbit(x))
c[x] += v;
return ;
}
inline int get(int x) {
int sum = 0;
for (; x; x -= lowbit(x))
sum += c[x];
return sum;
}
typedef std :: pair <int, int> pii;
std :: vector <pii> qst[maxn];
int ans[maxq];
int main() {
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
std :: fill(lst + 1, lst + maxv - 3, n + 1);
int q = read();
for (int i = 1; i <= q; ++i) {
int l = read(), r = read();
qst[r].emplace_back(l, i);
}
for (int r = 1; r <= n; ++r) {
int x = a[r];
add(lst[x], -1);
add(r, 1);
lst[x] = r;
for (pii q : qst[r]) {
int l = q.first, id = q.second;
ans[id] = get(r) - get(l - 1);
}
}
for (int i = 1; i <= q; ++i)
printf("%d\n", ans[i]);
return 0;
}
思路历程：
考虑区间询问。其实也就是让区间内所有 \(x\) 只被统计一次。
那么考虑一个数组 \(b\)。初始时 \(b\) 都是 \(1\)。然后对于一次询问 \([l, r]\)，如果在区间内有三个数 \(i, j, k\) 满足 \(a_i = a_j = a_k\)，那么我们只考虑让其中一个 \(b\) 变为 \(1\)，比如 \(b_i = 1\)，然后其他的 \(b_j = b_k = 0\)。类似这样的操作，只需要查询 \(b\) 在 \([l ,r]\) 内的区间和，就是答案。
那么具体来说让哪个值变为 \(1\) 呢？先考虑最左侧变为 \(1\)。
发现很难高效地完成上面那个 \(b\) 的变化操作。。。每次询问都需要扫一遍 \([l, r]\)，别太离谱了，，
那就考虑在整个数组上扫。然后考虑怎么应用到子区间。（丹钓战那题的思想）
发现不同的询问，某个元素的 \(b\) 值是不同的，比如 \((1, 2, 3, 3, 5)\)，\([4, 5]\) 的 \(b_4\) 需要是 \(1\)，但 \([3, 5]\) 的 \(b_4\) 就会变成 \(0\)。
其实想一下也就是 \(l \le 3\) 的询问里，\(b_4\) 变为 \(0\) 呗。那么肯定考虑离线询问了。
是否每次能回答的询问都是类似于 \(l \le \cdots\) 的形式？对。
上面那个例子中，所有 \(l \le 3\) 的询问的 \(b_4\) 为 \(0\)，\(l > 3\) 的询问 \(b_4\) 为 \(1\) 肯定是没有问题的。
考虑维护一个指针 \(L\)，倒着扫，每次扫到 \(a_L\)，检查一下之前有没有一个 \(a_k\) 等于这个 \(a_L\)，如果有就把那个 \(b_k\) 翻成 \(0\)。 然后回答所有左端点为 \(L\) 的询问。
要不翻转一下，维护一个指针 \(R\)。正着扫。（有点别扭）
考虑维护一个指针 \(R\)，每次扫到 \(a_R\)，检查一下之前有没有一个 \(a_k = a_R\)，若有，\(b_k\) 翻为 \(0\)。然后回答所有右端点为 \(R\) 的询问，询问如果是 \([L, R]\) 那就是求 \(b\) 的 \([L, R]\) 区间和。
\(b\) 树状数组加速即可。
标签：ch,int,luogu,询问,数组,区间,SDOI2009,P1972,考虑 From： https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p1972.html