【BZOJ】【1878】【SDOI2009】HH的项链

时间：2022-07-12 05:20:35

树状数组/前缀和

　　Orz lct1999

　　好神的做法。。。

　　先看下暴力的做法：对于区间[l,r]，我们依次扫过去，如果这个数是第一次出现，那么我们种类数+1。

　　我们发现：区间中相同的几个数，只有最左边那个才对答案有贡献。

　　那么我们O(n)预处理一个next数组，满足a[i]=a[next[i]]，且i~next[i]这一段中没有与a[i]相等的数。。。。其实就是 i 右边第一个跟a[i]相等的值的下标啦。。

　　再回头看下我们的询问：对答案有贡献的数的特点是：它在整个序列中第一次出现，或者它是区间外某个数的next。在区间中再次出现的数，next指向它的数也一定也在区间中。

　　

　　那么我们处理查询[l,r]时，我们可以将[1,l-1]的next[i]对答案的贡献+1，也就是我们维护一个ans数组，对ans[next[i]]++

　　答案就是ans[r]-ans[l-1]（都是前缀和）

　　对询问进行左端点排序，树状数组维护一下即可……

　　（然而感觉蒟蒻并没有讲清楚……大家可以去看zyf神犇的blog：http://www.cnblogs.com/zyfzyf/p/3935617.html

 /**************************************************************

     Problem: 1878

     User: Tunix

     Language: C++

     Result: Accepted

     Time:920 ms

     Memory:5768 kb

 ****************************************************************/

 //BZOJ 1878

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 typedef long long LL;

 inline int getint(){

     int r=,v=; char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;

     for(; isdigit(ch);ch=getchar()) v=v*-''+ch;

     return r*v;

 }

 const int N=,M=;

 /*******************template********************/

 int n,m,num,a[N],c[N],now[N],fi[N],next[N],ans[M];

 struct que{int l,r,num;}q[M];

 bool operator < (const que &a,const que &b){return a.l<b.l;}

 int b[N],d[N];

 void add(int x){

     d[x]++;

     if (!x) return;

     for(int i=x;i<=n;i+=i&(-i)) b[i]++;

 }

 int sum(int x){

     int r=;

     for(int i=x;i;i-=i&(-i)) r+=b[i];

     return r;

 }

 void init(){

     n=getint();

     F(i,,n) c[i]=a[i]=getint();

     sort(c+,c+n+);

     num=unique(c+,c+n+)-c-;

     F(i,,n){

         a[i]=lower_bound(c+,c+num+,a[i])-c;

         if (now[a[i]]){

             next[now[a[i]]]=i;

             now[a[i]]=i;

         }else{

             add(i);

             now[a[i]]=i;

         }

     }

     m=getint();

     F(i,,m) q[i].l=getint(),q[i].r=getint(),q[i].num=i;

 }

 void solve(){

     sort(q+,q+m+);

     int now=;

     F(i,,m){

         while(now<q[i].l){

             add(next[now]);

             now++;

         }

         ans[q[i].num]=sum(q[i].r)-sum(q[i].l-);

     }

     F(i,,m) printf("%d\n",ans[i]);

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("1878.in","r",stdin);

     freopen("1878.out","w",stdout);

 #endif

     init();

     solve();

     return ;

 }

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2079  Solved: 1032
[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。

Source

[Submit][Status][Discuss]

相关文章