明天就要上课了
这题是一个莫队+分块
据说莫队+树状数组会T掉
所以我就把整个答案按照权值分块卡卡常就做完了
目前bzoj用时为$20808ms$
数组开小wa两次我真是太弱了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005,block=300;
int n,m,s[N],ans[N*10],cnt[N],bk[N];
inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
inline int Gi(const int &x){return (x-1)/block+1;}
struct Query{
int l,r,a,b,id;
friend inline bool operator<(const Query &A,const Query &B){return Gi(A.l)<Gi(B.l)||(Gi(A.l)==Gi(B.l) && A.r<B.r);}
}que[N*10];
inline void Up(int x){
cnt[s[x]]++;
if(cnt[s[x]]==1)bk[Gi(s[x])]++;
}
inline void Down(int x){
cnt[s[x]]--;
if(cnt[s[x]]==0)bk[Gi(s[x])]--;
}
inline int Q(const int &l,const int &r){
int ls=Gi(l)+1,rs=Gi(r)-1,lv=Gi(l)*block,rv=(Gi(r)-1)*block+1,ans=0;
if(ls-rs==2)for(register int i=l;i<=r;i++)ans+=(cnt[i]>0);
else {
for(register int i=ls;i<=rs;i++)ans+=bk[i];
for(register int i=l;i<=lv;i++)ans+=(cnt[i]>0);
for(register int i=rv;i<=r;i++)ans+=(cnt[i]>0);
}
return ans;
}
int main(){
freopen("3809.in","r",stdin);
freopen("3809.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(s[i]);
for(register int i=1;i<=m;i++)Read(que[i].l),Read(que[i].r),Read(que[i].a),Read(que[i].b),que[i].id=i;
sort(que+1,que+m+1);
register int L=1,R=0;
for(register int i=1;i<=m;i++){
while(L>que[i].l)Up(--L);
while(L<que[i].l)Down(L++);
while(R>que[i].r)Down(R--);
while(R<que[i].r)Up(++R);
ans[que[i].id]=Q(que[i].a,que[i].b);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
评论 (0)
