[SDOI2009]HH的项链

Time Limit:4000MS  Memory Limit:65536K
Total Submit:4 Accepted:2
Case Time Limit:1000MS

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

Hint

对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。

Source

Day2
首先肯定在线算法是搞不出来的冏，所以离线处理。对每个位置维护到当前考虑到点有多少不同点个。然后每次考虑第i个数时，设Ai上一次出现在第p个。。那么p+1->i的答案全部+1，可以很方便地用树状数组维护。。PS。。把树状数组写成类的形式感觉真爽啊。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=50000+2,maxm=200000,maxd=1000000+1;
using namespace std;
typedef pair<int,int> ii;
int Ans[maxm],A[maxn],P[maxd],n,m;
vector<ii> E[maxn];
struct TArray
{
int A[maxn],n;
void Add(int p,int d)
{
for(;p<=n;p+=(p&-p))A[p]+=d;
}
void Add(int l,int r,int d)
{
Add(l,d);Add(r+1,-d);
}
void Set(int _n){n=_n;For(i,0,n)A[i]=0;}
int operator[](int i)
{
int ret=0;if(!i)return inf;
for(;i;i-=(i&-i))ret+=A[i];
return ret;
}
}T;
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);For(i,1,n)scanf("%d",A+i),P[A[i]]=0;
scanf("%d",&m);int l,r;rep(i,m)scanf("%d%d",&l,&r),E[r].pb(ii(l,i));
T.Set(n);
For(i,1,n)
{
int t=A[i],p=P[t]+1;P[t]=i;
T.Add(p,i,1);
rep(j,E[i].size())Ans[E[i][j].second]=T[E[i][j].first];
}
rep(i,m)printf("%dn",Ans[i]);
}