题解 P2709 【小B的询问】

· · 题解

这题其实是一个非常模板的无修改的莫队。

说下思路：

我们可以拿一个mp数组记录在一个区间内各种颜色出现的个数，然后就是跑一遍普通莫队。（加减时要注意平方）。

l记得要从1开始。

#include<bits/stdc++.h>
using namespace std;
struct data
{
    int x,y,id,ans;
}a[50010];
int gg,n,m,k,c[50010],b[50010],mp[50010],l=1,r,ans;
bool operator < (data a,data b)
{
    if(c[a.x]==c[b.x])
    {
        return a.y<b.y;
    }
    return a.x<b.x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    gg=pow(n,0.54);//据说是最快的分块方式
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        c[i]=(i-1)/gg+1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].id=i;
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)//处理（平方）
    {
        while(l<a[i].x)
        {
            ans-=mp[b[l]]*mp[b[l]];
            mp[b[l]]--;
            ans+=mp[b[l]]*mp[b[l]];
            l++;
        }
        while(l>a[i].x)
        {
            l--;
            ans-=mp[b[l]]*mp[b[l]];
            mp[b[l]]++;
            ans+=mp[b[l]]*mp[b[l]];
        }
        while(r>a[i].y)
        {
            ans-=mp[b[r]]*mp[b[r]];
            mp[b[r]]--;
            ans+=mp[b[r]]*mp[b[r]];
            r--;
        }
        while(r<a[i].y)
        {
            r++;
            ans-=mp[b[r]]*mp[b[r]];
            mp[b[r]]++;
            ans+=mp[b[r]]*mp[b[r]];
        }
        a[a[i].id].ans=ans;//按id来给答案
    }
    for(int i=1;i<=m;i++)//输出
    {
        printf("%d\n",a[i].ans);
    }
    return 0;
}