LG2709 小B的询问

莫队算法模板题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
/******************heading******************/

const int N=5e4+5;
int n,T,m,k;
int a[N];
struct data{int l,r,id;}q[N];
bool cmp(data x,data y){
    return x.l/T==y.l/T?x.r<y.r:x.l<y.l;
}

int l,r,cur;
int c[N],ans[N];
void addr(){cur+=2*c[a[++r]]+1, c[a[r]]++;}
void decl(){cur+=2*c[a[--l]]+1,c[a[l]]++;}
void decr(){cur+=-2*c[a[r]]+1, c[a[r--]]--;}
void addl(){cur+=-2*c[a[l]]+1, c[a[l++]]--;}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,n)scanf("%d",&a[i]);
    FOR(i,1,m)scanf("%d%d",&q[i].l,&q[i].r), q[i].id=i;
    T=sqrt(n);
    sort(q+1,q+m+1,cmp);
    l=r=1,c[a[1]]++,cur=1;//init
    FOR(i,1,m){
        while(r<q[i].r)addr();
        while(l>q[i].l)decl();
        while(r>q[i].r)decr();
        while(l<q[i].l)addl();
        ans[q[i].id]=cur;
    }
    FOR(i,1,m)printf("%d
",ans[i]);
    return 0;
}