cf D. Powerful array 莫队算法

D. Powerful array

题意:给定一个序列>>每次查询一个区间>>查询该区间内 出现过的数字*出现的次数的平方 的和

思路:学习莫队的第一题或者说小z的袜子是第一题>>

　　莫队算法主要是应用于区间离线操作>>>并且要求已知:[l,r]的值,能够在o(1)的时间内求出[l,r-1],[l+1,r]的值

　　时间复杂度 n^1.5;

说白了>>这个题也是一个模板题吧>>

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; const int M=1e6+10; int n,t,blo;ll tmp; struct Node{int l,r,id;}q[N]; ll ans[N];int a[N],num[M]; bool cmp(Node x,Node y){if(x.l/blo!=y.l/blo)return x.l/blo<y.l/blo;return x.r<y.r; } void add(int x){tmp-=1ll*a[x]*num[a[x]]*num[a[x]];num[a[x]]++;tmp+=1ll*a[x]*num[a[x]]*num[a[x]]; } void Remove(int x){tmp-=1ll*a[x]*num[a[x]]*num[a[x]];num[a[x]]--;tmp+=1ll*a[x]*num[a[x]]*num[a[x]]; } int main(){scanf("%d%d",&n,&t);blo=sqrt(n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=t;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+t+1,cmp);int nl=0,nr=0,l,r;for(int i=1;i<=t;i++){l=q[i].l,r=q[i].r;while(l<nl) add(--nl);while(r>nr) add(++nr);while(l>nl) Remove(nl++);while(r<nr) Remove(nr--);ans[q[i].id]=tmp;}for(int i=1;i<=t;i++)printf("%I64d\n",ans[i]);return 0; }

　　

转载于:https://www.cnblogs.com/vainglory/p/9177626.html

总结

以上是生活随笔为你收集整理的cf D. Powerful array 莫队算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。