C - Powerful array
题意:
给出一个序列,定义一个区间的power值为区间内的数出现的次数的平方乘以该数的和。对于区间1,2,1,它的power值为1*2*2+2*1*1=6。
分析:
稍微修改下莫队算法的模板就好了。
代码:
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int maxn=2e5+100; const int maxv=1e6+100; ll num; int n,q,block_size; ll res[maxn]; int arr[maxn],cnt[maxv]; struct Query { int l,r,id; bool operator < (const Query& rhs) const { if(l/block_size!=rhs.l/block_size){ return l/block_size<rhs.l/block_size; } return r<rhs.r; } }; Query query[maxn]; void add(int pos) { num-=(ll)cnt[arr[pos]]*cnt[arr[pos]]*arr[pos]; cnt[arr[pos]]++; num+=(ll)cnt[arr[pos]]*cnt[arr[pos]]*arr[pos]; } void del(int pos) { num-=(ll)cnt[arr[pos]]*cnt[arr[pos]]*arr[pos]; cnt[arr[pos]]--; num+=(ll)cnt[arr[pos]]*cnt[arr[pos]]*arr[pos]; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&q)!=EOF) { num=0; cls(cnt); block_size=sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); } for(int i=1;i<=q;i++){ query[i].id=i; scanf("%d%d",&query[i].l,&query[i].r); } sort(query+1,query+q+1); int L=query[1].l,R=L-1; for(int i=1;i<=q;i++){ while(L>query[i].l) add(--L); while(L<query[i].l) del(L++); while(R<query[i].r) add(++R); while(R>query[i].r) del(R--); res[query[i].id]=num; } for(int i=1;i<=q;i++){ printf("%lld ",res[i]); } } return 0; }