首页 > 其他 > 详细

luogu P2709 小B的询问 分块+莫队

时间:2020-05-21 09:36:31      阅读:33      评论:0      收藏:0      [点我收藏+]
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],belong[N];
int n,q,k;
inline int read()
{
    int k=0;
    char c;
    c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        k=(k<<3)+(k<<1)+c-0;
        c=getchar();
    }
    return k;
}
struct node
{
    int l,r;
    int id;
} e[N];
int cnt[N];
int Ans;
int ans[N];
inline bool cmp(node a,node b)
{
    if(belong[a.l]==belong[b.l])
        return belong[a.r]<belong[b.r];
    return belong[a.l]<belong[b.l];
}
inline void add(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    ++ cnt[a[x]];
    Ans+=cnt[a[x]]*cnt[a[x]];
}
inline void del(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    -- cnt[a[x]];
    Ans+=cnt[a[x]]*cnt[a[x]];
}
int main()
{
    n=read(),q=read(),k=read();
    int block = pow(n,0.5);
    for(register int i = 1; i <= n; ++ i)
    {
        a[i]=read();
        belong[i] = (i - 1) / block + 1;
    }
    for(register int i=1; i<=q; i++)
    {
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+1+q,cmp);
    int l = 1,r = 0;
    for(register int i = 1; i <= q; ++ i)
    {
        while(l < e[i].l)
            del(l ++);
        while(l > e[i].l)
            add(-- l);
        while(r < e[i].r)
            add(++ r);
        while(r > e[i].r)
            del(r --);
        ans[e[i].id] = Ans;
    }
    for(register int i = 1; i <= q; ++ i)
        cout<<ans[i]<<endl;
    return 0;
}

 

luogu P2709 小B的询问 分块+莫队

原文:https://www.cnblogs.com/QingyuYYYYY/p/12927522.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!