5
18
2016
0

[BZOJ3781] 小B的询问

莫队算法模版题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=50005;
 
int n,m,k,a[N],block_size,ans[N],c[N];
 
struct Query{
int l,r,block,id;
friend bool operator<(Query A,Query B){return A.block<B.block||(A.block==B.block && A.r<B.r);}
}q[N];
 
void Solve(){
int L=1,R=0,Ans=0;
for(int i=1;i<=m;i++){
    while(L<q[i].l){if(a[L])Ans-=2*c[a[L]]-1;c[a[L]]--;L++;}
    while(L>q[i].l){L--;c[a[L]]++;if(a[L])Ans+=2*c[a[L]]-1;}
    while(R<q[i].r){R++;c[a[R]]++;if(a[R])Ans+=2*c[a[R]]-1;}
    while(R>q[i].r){if(a[R])Ans-=2*c[a[R]]-1;c[a[R]]--;R--;}
    ans[q[i].id]=Ans;
}
}
 
int main(){
freopen("3781.in","r",stdin);
freopen("3781.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
block_size=(int)sqrt(m);
if(block_size<50)block_size=50;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>k)a[i]=0;}
for(int i=1;i<=m;i++){
    scanf("%d %d",&q[i].l,&q[i].r);
    q[i].block=(q[i].l+1)/block_size;
    q[i].id=i;
}
sort(q+1,q+m+1);
Solve();
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 537

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com