BZOJ1878-HH的项链（离线操作+树状数组）

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec   Memory Limit: 64 MB Submit: 4423   Solved: 2201 [ Submit][ Status][ Discuss]

Description

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

Input

第一行：一个整数N，表示项链的长度。  第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。  第三行：一个整数M，表示HH询问的个数。  接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。 N ≤ 50000，M ≤ 200000。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

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

Sample Output

2 2 4

HINT

题意：m次查询，每次询问区间[l r]中不同数的个数。

题解：对于区间中不同数的个数，两种做法，在线的话主席树搞搞吧（回头学一发Orz），这里采用离线的做法，

首先我们可以预处理出每个数上一次出现的位置，进而可以思考这样一个问题，对于一个区间中的数，在该区间左边出现的个数即为该区间中数的个数，想想便知，因此我们可以处理出前缀和来解决这个问题，对于一个数，我们可以在该数上一次出现的位置后面一个位置处+1，在当前位置后的位置处-1，利用一发前缀和便能在O（1）的情况下求出答案，然而此时是一个区间询问，首先我们就要想办法让区间变成线性的，这里采用按右端点排序（当然，左端点也可以，不过就是另一种预处理罢了），从左到右枚举右端点，然后更新区间的值（树状数组搞一发），之后根据处理出的前缀和来线性求值即可。

#include<map> #include<stack> #include<queue> #include<vector> #include<math.h> #include<time.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; typedef long long ll; #define inf 2147483647 #define mod 998244353 #define maxn 1000005 #define lowbit(x) (x&-x) #define eps 1e-6 int c[maxn],n,m,p[maxn],pos[maxn],b[maxn],ans[maxn]; struct node { int l,r,id; }a[maxn]; bool comp(node a,node b) { if(a.r==b.r) return a.l<b.l; return a.r<b.r; } void update(int k,int x) { while(k<=n) { c[k]+=x; k+=lowbit(k); } } int getsum(int x) { int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum; } int main(void) { int i,j,num=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&b[i]); p[i]=pos[b[i]]; pos[b[i]]=i; } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&a[i].l,&a[i].r); a[i].id=i; } sort(a+1,a+m+1,comp); for(i=1;i<=m;i++) { while(num<a[i].r) { num++; update(p[num]+1,1); if(num<n) update(num+1,-1); } ans[a[i].id]=getsum(a[i].l); } for(i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }