P1972 [SDOI2009]HH的项链
题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。
输入输出格式
输入格式:
第一行:一个整数N,表示项链的长度。
第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。
第三行:一个整数M,表示HH 询问的个数。
接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
输出格式:
M 行,每行一个整数,依次表示询问对应的答案。
输入输出样例
说明
数据范围:
对于100%的数据,N <= 500000,M <= 500000。
等会儿再思考一下dalao们主席树的做法QAQ
刚看题的时候觉得好像以前做的线段树合并求区间颜色段数,然后发现这道题似乎还要难些?
我们可以发现,对于一段区间,我们要统计$(i,j)$颜色种数的话,实际上只有每种颜色在$j$之前出现的最后一次可能可以起作用,它之前出现的所有同样颜色都可以忽略不计,只要统计到最后一次出现的就行了。
所以按右端点排序,用莫队的思想(左端点都不用移),每次向右拓展区间,把每种颜色上一次出现的位置删掉,然后到达当前右端点后,树状数组直接查询这段区间和即可。
#include<bits/stdc++.h>
using namespace std; int n, m, a[]; struct Node {
int l, r, id;
int ans;
} qus[];
bool cmp(Node a, Node b) { return a.r < b.r; }
bool cmp2(Node a, Node b) { return a.id < b.id; } int lowbit(int x) {
return x & -x;
} int pre[];
void add(int x, int d) {
for(int i = x; i <= ; i += lowbit(i))
pre[i] += d;
} int query(int x) {
int ans = ;
for(int i = x; i; i -= lowbit(i))
ans += pre[i];
return ans;
} int last[];
int main() {
scanf("%d", &n);
for(int i = ; i <= n; i ++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = ; i <= m; i ++)
scanf("%d%d", &qus[i].l, &qus[i].r), qus[i].id = i;
sort(qus + , qus + + m, cmp);
qus[].ans = query(qus[].r) - query(qus[].l - );
for(int i = ; i <= m; i ++) {
for(int j = qus[i-].r + ; j <= qus[i].r; j ++) {
if(last[a[j]]) add(last[a[j]], -);
add(j, );
last[a[j]] = j;
}
qus[i].ans = query(qus[i].r) - query(qus[i].l - );
}
sort(qus + , qus + + m, cmp2);
for(int i = ; i <= m; i ++) printf("%d\n", qus[i].ans);
return ;
}