CF86D-Powerful Array

简要题面

设一个序列的分值为每个数出现次数的平方乘这个数，给定一个长度为n序列，有m组询问$[l,r]$，求从第l个数到第r个数这个子序列的分值。

不需简要题解（其实就是直接放代码）

莫队裸题。

/*
Author: CNYALI_LK
LANG: C++
PROG: CF86D.cpp
*/
#include<bits/stdc++.h>
#define up(a,b,c) for (ll a(b),a##end(c);a<=a##end;++a)
#define down(a,c,b) for (ll a(b),a##end(c);a>=a##end;--a)
#define uup(a,c,b) for (ll a(b),a##end(c);a<=a##end;++a)
#define udown(a,b,c) for (ll a(b),a##end(c);a>=a##end;--a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
struct inout{
    static const ll ibufl=1<<25;
    static const ll obufl=1<<25;
    char in_buf[ibufl],out_buf[obufl],*inf,*ouf;
    ll no;
    operator bool(){
        return !no;
    }
    inout(){
        inf=in_buf;ouf=out_buf;
        no=0;
    }
    void init(){
        fread(in_buf,1,ibufl,stdin);
    }
    inout& operator >>(ll &a){
        ll fh=1;
        while(!(isdigit(*inf)||*inf=='-'||*inf=='\0'))++inf;
        if(*inf=='\0'){
            no=1;
            a=0;
            return *this;
        }
        if(*inf=='-')fh=-1,++inf;
        a=0;
        while(isdigit(*inf)){a=a*10+*inf-'0';++inf;}
        a*=fh;
        return *this;
    }
    inout& operator >>(char &a){
        while(*inf==' '||*inf=='\n')++inf;
        if(*inf=='\0'){
            no=1;
            a=0;
            return *this;
        }

        a=*inf;
        ++inf;
        return *this;
    }
    inout& operator >>(char *a){
        while(*inf==' '||*inf=='\n')++inf;
        if(*inf=0){
            a='\0';
            no=1;
            return *this;
        }
        while(!(*inf==' '||*inf=='\n'||*inf=='\0')){*a=*inf;++inf;++a;}
        *a='\0';
        return *this;
    }

    inout& operator >>(double &a){
        ll fh=1;
        double s;
        while(!(isdigit(*inf)||*inf=='-'||*inf=='.'||*inf=='\0'))++inf;
        if(*inf=='\0'){
            a=0;
            no=1;
            return *this;
        }
        if(*inf=='-')fh=-1,++inf;
        a=0;
        while(isdigit(*inf)){a=a*10+*inf-'0';++inf;}
        if(*inf=='.'){
            s=0.1;
            ++inf;
            while(isdigit(*inf)){
                a+=s*(*inf-'0');
                ++inf;
                s*=0.1;
            }
        }
        if(*inf=='E'||*inf=='e'){
            ll ss;
            ++inf;
            *this>>ss;
            if(ss>0){
                while(ss){
                    --ss;
                    a*=10;
                }
            }
            if(ss<0){
                while(ss){
                    ++ss;
                    a/=10;
                }
            }
            
        }
        a*=fh;
        return *this;
    }
    void writell(ll x){
        if(x/10)writell(x/10);
        *ouf=x%10+'0';
        ++ouf;
    }
    inout& operator <<(ll a){
        
        if(a<0){*ouf='-';++ouf;a=-a;}
        writell(a);
        return *this;
    }
    static const ll sz=7;
    inout& operator <<(char a){
        *ouf=a;++ouf;
        return *this;
    }
    inout& operator <<(char *a){
        while(*a){
            *ouf=*a;
            ++ouf;
            ++a;
        }
        return *this;
    }
    inout& operator <<(double a){
        if(a<-eps){*ouf='-';++ouf;a=-a;}
        writell((ll)a);
        a-=(ll)a;
        *ouf='.';
        ++ouf;
        up(i,1,sz){
            a=a*10;
            *ouf=(ll)a+'0';
            ++ouf;
            a-=(ll)a;
        }
        return *this;
    }
    void out(){
        fwrite(out_buf,1,ouf-out_buf,stdout);
        ouf=out_buf;
    }
};
inout io;
struct ques{
    ll l,r,t;
};
ques ask[201010];
ll askl(ques a,ques b){return a.l<b.l||a.l==b.l&&a.r<b.r;}
ll askr(ques a,ques b){return a.r<b.r||a.r==b.r&&a.l<b.l;}
ll a[201010],sum[1001010],tot,ans[201010];
void add(ll x){tot+=x*(sum[x]*2+1);++sum[x];}
void rm(ll x){tot-=x*(sum[x]*2-1);--sum[x];}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    io.init();
    ll n,s,l,r,m;
    io>>n>>m;
    up(i,1,n)io>>a[i];
    up(i,1,m){
        io>>ask[i].l>>ask[i].r;
        ask[i].t=i;
    }
    sort(ask+1,ask+m+1,askl);
    l=1,r=1000;
    ll mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(sqr(mid)<=m)l=mid+1;
        else r=mid-1;
    }
    s=l-1;
    for(ll i=1,j=s;i<=m;i+=s,j=mmin(j+s,m)){sort(ask+i,ask+j+1,askr);}
    l=ask[1].l;
    r=ask[1].r;
    up(i,l,r){
        add(a[i]);
    }
    ans[ask[1].t]=tot;
    up(i,2,m){
        while(l>ask[i].l){--l;add(a[l]);}
        while(r<ask[i].r){++r;add(a[r]);}
        while(l<ask[i].l){rm(a[l]);++l;}
        while(r>ask[i].r){rm(a[r]);--r;}    
        ans[ask[i].t]=tot;
    }
    up(i,1,m)io<<ans[i]<<endl;

    io.out();
    return 0;
}