BZOJ 3781: 小B的询问 [莫队]

时间：2024-01-18 16:22:32

求区间每种颜色出现次数平方和

写裸题练手

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=5e4+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,a[N],Q,k, block,m,pos[N];

struct meow{

    int l,r,id;

    bool operator <(const meow &x) const {return pos[l]<pos[x.l] || (pos[l]==pos[x.l] && r<x.r);}

}q[N];

int c[N]; ll now=,ans[N];

inline void add(int x) {now+=*c[a[x]]+; c[a[x]]++;}

inline void del(int x) {now-=*c[a[x]]-; c[a[x]]--;}

void solve(){

    int l=,r=;

    for(int i=;i<=Q;i++){

        while(r<q[i].r) r++, add(r);

        while(r>q[i].r) del(r), r--;

        while(l<q[i].l) del(l), l++;

        while(l>q[i].l) l--, add(l);

        ans[q[i].id]=now;

    }

}

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();k=read();

    block=sqrt(n); m=(n-)/block+;

    for(int i=;i<=n;i++) a[i]=read(), pos[i]=(i-)/block+;

    for(int i=;i<=Q;i++) q[i].l=read(), q[i].r=read(), q[i].id=i;

    sort(q+, q++Q);

    solve();

    for(int i=;i<=Q;i++) printf("%lld\n",ans[i]);

}

相关文章