题目
题目描述
萧芸斓是Z国的公主，平时的一大爱好是采花。
今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。
花园足够大，容纳了 \(n\) 朵花，花有 \(c\) 种颜色（用整数 \(1-c\) 表示），且花是排成一排的，以便于公主采花。
公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。
由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 \(m\) 个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。
输入描述
第一行三个空格隔开的整数 \(n,c\) 以及 \(m\) 。
接下来一行 \(n\) 个空格隔开的整数，每个数在 \([1, c]\) 间，第 \(i\)个数表示第 \(i\) 朵花的颜色。
接下来 \(m\) 行每行两个空格隔开的整数 \(l\) 和 \(r（l ≤ r）\) ，表示女仆安排的行程为公主经过第 \(l\) 到第 \(r\) 朵花进行采花。
输出描述
共 \(m\) 行，每行一个整数，第 \(i\) 个数表示公主在女仆的第 \(i\) 个行程中能采到的花的颜色数。
示例1
输入
5 3 5
1 2 2 3 1
1 5
1 2
2 2
2 3
3 5
输出
2
0
0
1
0
说明
【样例说明】
询问[1, 5]：公主采颜色为1和2的花，由于颜色3的花只有一朵，公主不采；询问[1, 2]：颜色1和颜色2的花均只有一朵，公主不采；
询问[2, 2]：颜色2的花只有一朵，公主不采；
询问[2, 3]：由于颜色2的花有两朵，公主采颜色2的花；
询问[3, 5]：颜色1、2、3的花各一朵，公主不采。
备注
本题采用多测试点捆绑测试，共有两个子任务。对于子任务1，分值为100 分，保证 \(1 \leq n, c, m \leq 3 \times 10^5\)。对于子任务2，分值为100 分，保证 \(1 \leq n, c, m \leq 2 \times 10^6\) 。对于全部的测试点，保证 \(1 \leq x_i \leq c\)，\(1 \leq l \leq r \leq n\) 。
题解
知识点：树状数组，枚举，离线。
我们从左往右走，发现每遇到一朵花时，他上上次出现的后一个位置到上次出现位置之间的作为左端点时，答案会加 \(2\) ；上次位置到起始点的位置作为左端点时，答案会加 \(1\) 。
因此，将询问按右端点排序，维护上次出现位置 \(lst\) 和上上次出现位置 \(lstlst\) ，用树状数组维护答案即可。
时间复杂度 \(O((n+m) \log n + m \log m)\)
空间复杂度 \(O(n+m)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
struct Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T::e());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T::e();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
T query(int l, int r) { return query(r) - query(l - 1); }
};
struct T {
int val;
static T e() { return { 0 }; }
T &operator+=(const T &x) { return val += x.val, *this; }
friend T operator-(const T &a, const T &b) { return { a.val - b.val }; }
};
int a[2000007];
struct Query {
int l, r;
int id;
}q[2000007];
int lst[2000007], lstlst[2000007];
int ans[2000007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, c, m;
cin >> n >> c >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= m;i++) {
int l, r;
cin >> l >> r;
q[i] = { l,r,i };
}
sort(q + 1, q + m + 1, [&](const Query &a, const Query &b) {return a.r < b.r;});
Fenwick<T> fw(n);
int pos = 1;
for (int i = 1;i <= n;i++) {
if (!lst[a[i]]) lst[a[i]] = i;
else if (!lstlst[a[i]]) {
fw.update(1, { 1 });
fw.update(lst[a[i]] + 1, { -1 });
lstlst[a[i]] = lst[a[i]];
lst[a[i]] = i;
}
else {
fw.update(lstlst[a[i]] + 1, { 1 });
fw.update(lst[a[i]] + 1, { -1 });
lstlst[a[i]] = lst[a[i]];
lst[a[i]] = i;
}
while (pos <= m && q[pos].r == i) ans[q[pos].id] = fw.query(1, q[pos].l).val, pos++;
}
for (int i = 1;i <= m;i++) cout << ans[i] << '\n';
return 0;
}