Codeforces 86D Powerful array

题目链接http://codeforces.com/problemset/problem/86/D

题意:给你一个序列和若干询问,每次询问[L,R]求这个区间内所有数各自出现的次数的平方再乘上它们自己之和。

思路:莫队算法裸题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
const int N=200000+10;
const int M=1000000+10;
int n,t,l,r,i,sz,a[N],f[M];
ll res,ans[M];
struct Query{
    int l,r,id,pos;
    bool operator<(const Query&rhs)const{
        return pos^rhs.pos?pos<rhs.pos:pos&1?r<rhs.r:r>rhs.r;
    }
}q[N];
void revise(int x,int val){
    res-=1LL*x*f[x]*f[x];
    f[x]+=val;
    res+=1LL*x*f[x]*f[x];
}
int main(){
    read(n),read(t);
    sz=sqrt(n+0.5);
    for (i=1;i<=n;i++) read(a[i]);
    for (i=1;i<=t;i++){
        read(q[i].l),read(q[i].r);
        q[i].id=i;
        q[i].pos=(q[i].l-1)/sz+1;
    }
    sort(q+1,q+1+t);
    for (i=l=1,r=0;i<=t;i++){
        int L=q[i].l,R=q[i].r;
        while (r<R) revise(a[++r],1);
        while (l>L) revise(a[--l],1);
        while (r>R) revise(a[r--],-1);
        while (l<L) revise(a[l++],-1);
        ans[q[i].id]=res;
    }
    for (i=1;i<=t;i++) printf("%lld\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注