洛谷P1972 [SDOI2009]HH的项链_综合

题目描述

??P1972 [SDOI2009]HH的项链
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 $n$ ，表示项链长度。
第二行 $n$ 个正整数 $a_i$ ，表示项链中第 $i$ 个贝壳的种类。
第三行一个整数 $m$ ，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$ ，表示询问的区间。

输出格式

输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

输出格式样例

输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出 #2

2
2
4

说明/提示

对于 20%20% 的数据， $1\le n,m\leq 5000$ ；
对于 40%40% 的数据， $1\le n,m\leq 10^5$ ；
对于 60%60% 的数据， $1\le n,m\leq 5\times10^5$ ；
对于 100%100% 的数据， $1\le n,m,a_i \leq 10^6,1\le l \le r \le n$ 。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB。

解题思路

??使用树状数组进行区间求和。
首先对需要访问的区间进行归类，按照right相等进行归类，因为对于区间[left, right]来说，当right值相等时，对于重复的数字，最右侧的数字才是真正有效的。举例：对于序列5 2 5 3 5来说，访问区间[1,5]和区间[2,5]实质上都会忽略左侧重复的1，即实际序列可处理为0 2 0 3 5。
其次对数据进行处理，将右侧不重复的位置上的数字替换为1，这样便可利用求区间和来求不重复数字的个数。举例：上面的序列可替换为0 1 0 1 1，这样求区间[2,5]中有多少不相同的数字即为求区间和，即为3。

??因此，先将访问区间数据读入并存起来，使用sort()按照right从小到大进行排序。遍历排序好的访问区间数据，当right值发生更改时，更新原有的树状数组。更新过程需要注意：第一，更新过程仅需要从上一次right的下一个数据开始到本次right值位置结束；第二，为保证原有的重复数据被更新，使用table[]数组来记录每一个数据的最新位置，举例：对于序列5 2 5 3 5，在访问区间[1,3]时有table[5]=3，在访问区间[2,5]时由于更新，此时table[5]=5同时将树状数组位置3的值更新为0，即将树状数组中table[5]位置的值更新为0；对于没有重复的数据，直接更新树状数组值为1即可。
代码如下：

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX 1000002int n, m;
int shell[MAX], cp_shell[MAX], table[MAX], res[MAX]; //shell存原始数据，cp_shell为树状数组，table记录数据最后出现的位置，res记录第i次访问数据的结果
struct visit{int left, right;int num;  //第i个数据
}visit[MAX];   //记录访问数据int read(){ //快读char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();int res = 0;while(ch >= '0' && ch <= '9'){res = res * 10 + ch - '0';ch = getchar();} return res;
}bool cmp(struct visit a, struct visit b){  //按照right值进行从小到大排序return a.right < b.right;
}/*---树状数组操作---*/
int lowbit(int num){return num & (-num);
} void update(int position, int add_num){  //更新while(position <= n){cp_shell[position] += add_num;position += lowbit(position);}
}int sum(int position){  //求数组cp_shell前position个数据的和int res = 0;while(position > 0){res += cp_shell[position];position -= lowbit(position);}return res;
}
/*------------------*/ int main(){//读数据scanf("%d", &n);for(int i = 1; i <= n; i++){shell[i] = read();}m = read();for(int i = 0; i < m; i++){visit[i].left = read();visit[i].right = read();visit[i].num = i;}//按照right进行分类排序sort(visit, visit + m, cmp);//遍历访问数据int right = 0, next = 1;for(int i = 0; i < m; i++){if(visit[i].right != right){  //当right值变化时right = visit[i].right;  //更新right值//从上一个right + 1开始更新树状数组for(int j = next; j <= right; j++){if(table[shell[j]]) update(table[shell[j]], -1);  //当更新区间有和前面重复的数据时，将上一个数据对应位置更新为0table[shell[j]] = j;  //若没有重复，则更新该数据最后出现的位置为当前位置update(j, 1);  //同时更新该位置树状数组数据为1}next = right + 1;   //记录下一次更新数据的起始位置为当前right + 1}res[visit[i].num] = sum(visit[i].right) - sum(visit[i].left - 1);  //由于对访问区间结构体进行过排序，因此不直接输出，而是将结果存入res[]数组中}//按顺序输出for(int i = 0; i < m; i++){printf("%d\n", res[i]);}return 0;
}

参考资料

树状数组详解
洛谷题解