洛谷 P1972 [SDOI2009]HH的项链
JDOJ 2897: [SDOI2009]HH的项链 Day2 T1
Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解 决这个问题。
Input
第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
Output
M行，每行一个整数，依次表示询问对应的答案。
Sample Input
6 1 2 3 4 3 5 3 1 2 3 5 2 6
Sample Output
2 2 4
题解：
离线的树状数组。
这里顺便介绍一下什么是离线算法》》
所谓离线算法，顾名思义，就是 智商不在线的算法 已经知道数据之后，在数据基础上进行处理的算法。说白了点，就是人家先把要问的问题告诉你，你针对问题做一系列处理，最后出解。
然后我们想一想这个东西怎么跟树状数组结合在一起。
首先看到区间，我们想到离线的算法就是针对这所有的问题而进行解答，而这个问题又是针对于同一个序列上的许多区间，那我们正常的思路就是想到，能否通过一定的处理，使得所有的区间扫一遍就能出所有的解？
排序。对。
我们需要把所有的区间变得有序，那么我们使用结构体存储每一个问题的左端点右端点和问题的编号。然后按照右端点给所有的问题进行排序。最后我们使用树状数组，这个树状数组表示的是前i个元素中不同于当前元素的个数。
最后我们就可以拿前缀和的思想解决问题，就是getsum(r)-getsum(l-1)，统计得出答案。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int c[500001],a[500001],ans[500001],v[500001];
int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
struct node
{
int l,r,id;
}q[500001];
bool cmp(node a,node b)
{
return a.r<b.r;
}
void fix(int x,int p)
{
for(int i=x;i<=n;i+=i&-i)
c[i]+=p;
}
int getsum(int x)
{
int ret=0;
for(int i=x;i;i-=i&-i)
ret+=c[i];
return ret;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m=read();
for(int i=1;i<=m;i++)
{
q[i].l=read();
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int nxt=1;
for(int i=1;i<=m;i++)
{
for(int j=nxt;j<=q[i].r;j++)
{
if(v[a[j]])
fix(v[a[j]],-1);
fix(j,1);
v[a[j]]=j;
}
nxt=q[i].r+1;
ans[q[i].id]=getsum(q[i].r)-getsum(q[i].l-1);
}
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}