题解 CF86D 【Powerful array】

· · 题解

这是莫队算法的裸题。关于莫队的介绍见这篇blog。

一般可用莫队做的题满足以下条件：

  1. 离线。（其实是有在线莫队的，见洛谷日报 183 期）
  2. 将已处理的区间由 [l,r] 转移为 [l \pm 1,r] 或 [l,r \pm 1] 是 \Theta(1) 的。

本题要求求出出现次数的平方乘以其出现的值。这和P2709 小B的询问很像。在转移时，我们可以用平方差公式。

设左指针为 lp，右指针为 rp，k 在 [lp,rp] 中出现 cnt_k 次。具体操作如下：

  1. 左端点向左移，lp \leftarrow lp-1，cnt_{a_{lp}} \leftarrow cnt_{a_{lp}}+1，res \leftarrow res+(2 \times cnt_{a_{lp}} -1) \times a_{lp}
  2. 右端点向右移，rp \leftarrow rp+1，cnt_{a_{rp}} \leftarrow cnt_{a_{rp}}+1，res \leftarrow res+(2 \times cnt_{a_{rp}} -1) \times a_{rp}
  3. 左端点向左移，res \leftarrow res+(2 \times cnt_{a_{lp}} -1) \times a_{lp}，cnt_{a_{lp}} \leftarrow nt_{a_{lp}}-1，lp \leftarrow lp+1
  4. 右端点向右移，res \leftarrow res+(2 \times cnt_{a_{rp}} -1) \times a_{rp}，cnt_{a_{rp}} \leftarrow cnt_{a_{rp}}-1，rp \leftarrow rp-1
  5. while(1)rp++;

Code:

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define neinf 0xc0c0c0c0
#define inf 0x3f3f3f3f
#define ll long long
#define reg register
#define db double
#define il inline
#define gc getchar
#define pc putchar
#define HgS 1000000007
il int rd()
{
    reg int res=0,lab=1;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')lab=-lab;ch=getchar();}
    while(ch>='0'&&ch<='9')
        res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
    return res*lab;
}
il void prt(ll x,char t)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)prt(x/10,0),x%=10;
    putchar(x|48);
    if(t)putchar(t);
}
#define ar 1000000
#define len 200000
#define siz 444
#define cp(x) ((x-1)/siz+1)
int n,a[len+5],q,tm[ar+5];
ll ans[len+5];
struct query
{
    int l,r,id;
    query(){l=r=id=0;}
    query(int _l,int _r,int _id){l=_l;r=_r;id=_id;}
}qr[len+5];
#define lq(i) ((qr+(i))->l)
#define rq(i) ((qr+(i))->r)
bool cmp(query x,query y)
{
    return cp(x.l)<cp(y.l)||(cp(x.l)==cp(y.l)&&
        ((cp(x.l)&1)?x.r<y.r:x.r>y.r));
}
int main()
{
    n=rd();q=rd();
    for(int i=1;i<=n;++i)a[i]=rd();
    for(int i=1;i<=q;++i)
    {
        int tl=rd(),tr=rd();
        qr[i]=query(tl,tr,i);
    }
    sort(qr+1,qr+1+q,cmp);
    reg int lt=1,rt=0;
    reg ll res=0;
    for(int i=1;i<=q;++i)
    {
        while(lt>lq(i))
            res+=(((++tm[a[--lt]])<<1)-1)*a[lt];
        while(rt<rq(i))
            res+=(((++tm[a[++rt]])<<1)-1)*a[rt];
        while(lt<lq(i))
            res-=a[lt]*(((tm[a[lt++]]--)<<1)-1);
        while(rt>rq(i))
            res-=a[rt]*(((tm[a[rt--]]--)<<1)-1);
        ans[qr[i].id]=res;
    }
    for(int i=1;i<=q;++i)prt(ans[i],'\n');
    return 0;
}