BZOJ 1878: [SDOI2009]HH的项链 树状数组 离线维护

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec  Memory Limit: 64 MB Submit: 3900  Solved: 1949 [Submit][Status][Discuss]

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。

比较懒，把树状数组的题放到线段树里吧。。。希望我以后能记得

我是看了hzwer的题解才全搞懂

维护每个数字与之相等的最近数字下标，每组相等数字的最小下标

用树状数组维护前缀和

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<iomanip> using namespace std; const int N=50010; const int M=200010; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,a[N],pos[1000009],nt[N],c[N],ans[M]; struct qy{int l,r,id;}q[M]; inline void update(int x,int v) {for(;x<=n;x+=(x&-x))c[x]+=v;} inline int query(int x) { int sum=0; for(;x;x-=(x&-x))sum+=c[x]; return sum; } inline bool cmp1(qy a,qy b) {return a.l==b.l?a.r<b.r:a.l<b.l;} inline bool cmp2(qy a,qy b) {return a.id<b.id;} int main() { n=read();int maxn=0; for(int i=1;i<=n;i++)a[i]=read(),maxn=max(maxn,a[i]); for(int i=n;i>=1;i--)nt[i]=pos[a[i]],pos[a[i]]=i; for(int i=1;i<=maxn;i++)if(pos[i])update(pos[i],1);//（那句if加完就对了，一头雾水） m=read();int x,y; for(int i=1;i<=m;i++)x=read(),y=read(),q[i]=(qy){x,y,i}; sort(q+1,q+1+m,cmp1); int now=1; for(int i=1;i<=m;i++) { while(now<q[i].l) { if(nt[now])update(nt[now],1); now++; } ans[q[i].id]=query(q[i].r)-query(q[i].l-1); } for(int i=1;i<=m;i++)printf("%d\n",ans[i]); }