bzoj3809 Gty的二逼妹子序列

3809: Gty的二逼妹子序列

Time Limit: 80 Sec   Memory Limit: 28 MB Submit: 1504   Solved: 436 [ Submit][ Status][ Discuss]

Description

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。   对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。   为了方便，我们规定妹子们的美丽度全都在[1,n]中。   给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。

 

Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。   第二行包括n个整数s1...sn(1<=si<=n)。   接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。   保证涉及的所有数在C++的int内。   保证输入合法。

 

Output

对每个询问，单独输出一行，表示sl...sr中权值∈[a,b]的权值的种类数。

 

Sample Input

10 10 4 4 5 1 4 1 5 1 2 1 5 9 1 2 3 4 7 9 4 4 2 5 2 3 4 7 5 10 4 4 3 9 1 1 1 4 5 9 8 9 3 3 2 2 1 6 8 9 1 4

Sample Output

2 0 0 2 1 1 1 0 1 2

HINT

 

样例的部分解释：   5 9 1 2 子序列为4 1 5 1 2 在[1,2]里的权值有1,1,2，有2种，因此答案为2。   3 4 7 9 子序列为5 1 在[7,9]里的权值有5，有1种，因此答案为1。   4 4 2 5 子序列为1 没有权值在[2,5]中的，因此答案为0。   2 3 4 7 子序列为4 5 权值在[4,7]中的有4,5，因此答案为2。   建议使用输入/输出优化。

 

 

Source

  [ Submit][ Status][ Discuss]

莫队+树状数组

把序列分块后记录每个数字的个数

加入一个数字后如果那个数字的cnt为1就在树状数组里加入

删除后如果那个数字的cnt为0就在树状数组里删除

代码:

#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define CH c=getchar() #define For(i,x,y) for(int i=x;i<=y;++i) using namespace std; const int N = 1e5+5; const int Block_Size = 333/2; inline int read(){     char CH;bool f=0;for(;!isdigit(c);CH) if(c=='-') f=1;     int x=0;for(;isdigit(c);CH) x=(x<<1)+(x<<3)+c-48;return f?-x:x; } int block[N]; int a[N]; int cnt[N]; int ans[1000005]; struct TreeArray{     #define lowbit(x) (x&-x)     int c[N];     void del(int x){         cnt[x]--;if(cnt[x]!=0)return;         for(int i=x;i<N;i+=lowbit(i)) c[i]--;     }     void ins(int x){         cnt[x]++;if(cnt[x]>1)return;         for(int i=x;i<N;i+=lowbit(i)) c[i]++;     }     int sum(int x){         int res=0;         for(int i=x;i;i-=lowbit(i)) res+=c[i];         return res;     } }T; struct Que{     int l,r,rk,u,v;     void get(int i){         rk=i;l=read();r=read();u=read();v=read();     }     bool operator < (const Que&b)const{return block[l]<block[b.l]||block[l]==block[b.l]&&r<b.r;} }q[1000005]; int main(){     int n=read(),m=read();     int _b = 1;     For(i,1,n){         if(i%Block_Size==0)++_b;         block[i]=_b;     }     For(i,1,n) a[i]=read();     For(i,1,m) q[i].get(i);     sort(q+1,q+m+1);     _b=0;int maxr=0,nowl=0;     For(Q,1,m){         int l=q[Q].l,r=q[Q].r,u=q[Q].u,v=q[Q].v;         if(block[l]==_b){             For(i,maxr+1,r) T.ins(a[i]);             if(l<nowl) For(i,l,nowl-1) T.ins(a[i]);             else For(i,nowl,l-1) T.del(a[i]);             ans[q[Q].rk]=T.sum(v)-T.sum(u-1);             maxr=r;nowl=l;         }         else{             _b=block[l];             if(Q>1)For(i,nowl,maxr) T.del(a[i]);             nowl=l,maxr=r;             For(i,l,r) T.ins(a[i]);             ans[q[Q].rk]=T.sum(v)-T.sum(u-1);         }     }     For(i,1,m) printf("%d\n",ans[i]); }

 

转载于:https://www.cnblogs.com/rwy233/p/6337427.html

相关资源：数据结构—成绩单生成器