BZOJ[3781]小B的询问 莫队

传送门ber~

莫队算法直接上
按在同一个块内按右端点排序，不在同一个块按所在块的编号排序将询问按左端点排序
枚举询问，不断移动左右端点，按这种顺序可以保证复杂度为$n^{1.5}$

代码如下：

#include
#include
#include
#include
#define N 50050
using namespace std;
inline int read(){int x=0,f=1;char c;do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));return x*f;
}
typedef long long LL;
int n,m,k,l,r,Block_size;
int a[N],num[N],block[N];
LL ans[N],tmp;
struct Query{int x,y,id;
}b[N];
inline bool cmp(Query a,Query b){return block[a.x]==block[b.x]?a.yinline void add(int x,int y){tmp-=num[x]*num[x];num[x]+=y;tmp+=num[x]*num[x];
}
int main(){n=read();m=read();k=read();Block_size=sqrt(n);for(int i=1;i<=n;i++){a[i]=read();block[i]=(i-1)/Block_size+1;}for(int i=1;i<=m;i++){b[i].id=i;b[i].x=read(),b[i].y=read();}sort(b+1,b+m+1,cmp);l=1;for(int i=1;i<=m;i++){while(l1);while(l>b[i].x) add(a[--l],1);while(r1);while(r>b[i].y) add(a[r--],-1);ans[b[i].id]=tmp;}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！