[HEOI2012]采花
题目描述
萧薰儿是古国的公主，平时的一大爱好是采花。
今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。
花园足够大，容纳了 $n$ 朵花，共有 $c$ 种颜色，用整数 $1 \sim c$ 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。
由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 $m$ 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。
输入格式
输入的第一行是三个用空格隔开的整数，分别代表花的个数 $n$，花的颜色数 $c$，以及行程数 $m$。
输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 朵花的颜色 $x_i$。
第 $3$ 行到第 $(m + 2)$ 行，每行两个整数 $l, r$，第 $(i + 2)$ 行的数字代表第 $i$ 次行程为第 $l$ 到第 $r$ 朵花。
输出格式
共输出 $m$ 行，每行一个整数。第 $i$ 行的整数代表第 $i$ 次行程公主能采到的花共有几种不同的颜色。
样例 #1
样例输入 #1
5 3 5
1 2 2 3 1
1 5
1 2
2 2
2 3
3 5
样例输出 #1
2
0
0
1
0
提示
输入输出样例 $1$ 解释
共有五朵花，颜色分别为 $1,2,2,3,1$。
对于第一次行程，公主采花的区间为 $[1, 5]$，可以采位置 $1,2,3,~5$ 处的花，共有 $1$ 和 $2$ 两种不同的颜色。
对于第二次行程，公主采花的区间为 $[1, 2]$，但是颜色为 $1$ 和 $2$ 的花都只出现了一次，因此公主无花可采。
对于第三次行程，公主采花的区间为 $[2, 2]$，但是颜色为 $2$ 的花只出现了一次，公主无花可采。
对于第四次行程，公主采花的区间为 $[2, 3]$，可以采 $2,~3$ 位置的花，只有 $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$。
思路：离线化处理，在将询问按照左端点从大到小排序，处理每个询问。
思路类似于：hdu-4630(树状数组) - 魏老6 - 博客园 (cnblogs.com)
但多了一步删除操作。
代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 5000000
#define M (int)1e8-3
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline ULL read() {
ULL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void print(ULL x) {
if (x > 9)print(x / 10);
putchar(x % 10 ^ 48);
}
int n, m, arr[N], tree[N],ans[N],k,last[N],old[N];
struct node
{
int l, r, i;
bool operator < (const node& a)const
{
return l > a.l;
}
}qu[N];
void update(int x, int d)
{
while (x <= N)
{
tree[x] += d;
x += lowbit(x);
}
}
int sum(int x)
{
int res = 0;
while (x)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}
int main()
{
n = read(), k = read(), m = read();
for (int i = 1; i <= n; i++)
{
arr[i] = read();
}
for (int i = 1; i <= m; i++)
{
qu[i].l = read(), qu[i].r = read(), qu[i].i = i;
}
sort(qu + 1, qu + 1 + m);
int j = 1;
for (int i = n; i >= 1; i--)
{
if (last[arr[i]])
{
update(last[arr[i]], 1);
if (old[arr[i]])
{
update(old[arr[i]], -1);
}
old[arr[i]] = last[arr[i]];
}
last[arr[i]] = i;
while (qu[j].l >= i)
{
ans[qu[j].i] = sum(qu[j].r) - sum(qu[j].l - 1);
j++;
if (j > m)break;
}
}
for (int i = 1; i <= m; i++)
{
printf("%d\n", ans[i]);
}
return 0;
}