莫队算法 - StarCried 的狼窝

莫队算法是一种暴力分块的算法，它能够减少移动次数提高效率。

使用需要转化在线算法为离线算法。具体见下方题目的题解。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#include<cmath>
using namespace std;
inline int read()
{
    int x=0,w=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
const int maxn=5e4+5;
int numb[maxn],a[maxn];
struct query{
    int l,r,id,pos;
    long long ans;
    bool operator < (const query& zp) const
    {
        return pos<zp.pos||pos==zp.pos&&r<zp.r;
     } 
}q[maxn];
int n,m,k;
long long Ans[maxn];
long long ans;
inline void update(int x,int sign)
{
    ans-=numb[a[x]]*numb[a[x]];
    numb[a[x]]+=sign;
    ans+=numb[a[x]]*numb[a[x]];
}
inline void solve()
{
    int l=1,r=0;//这个位置选得很好
    //不必担心lr同加或者同减的状况，都会被记录并抵消 
    for(int i=1;i<=m;i++)
    {
        while(l<q[i].l){update(l,-1);l++;}
        while(l>q[i].l){update(l-1,1);l--;}//注意位置 
        while(r<q[i].r){update(r+1,1);r++;}
        while(r>q[i].r){update(r,-1);r--;}
        Ans[q[i].id]=ans;
    }
}
int main()
{
    n=read(),m=read(),k=read();
    int size=sqrt(n);
    int cnt=n/size+(n%size)>0;
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=m;i++)
    {
        q[i]=(query){read(),read(),i};
        q[i].pos=(q[i].l-1)/size+1;
    }
    sort(q+1,q+1+m);
    solve();
    for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
    return 0;
}