普通莫队

洛谷P2709 https://www.luogu.com.cn/problem/P2709

// Problem: P2709 小B的询问
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2709
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f; 
struct Query {
    ll l,r,id,block;
    bool operator < (const Query& q)const//重写<运算符适应sort的规则
    {
       if(block==q.block)
          return r<q.r;
       else
          return block<q.block;
    }
}q[N];
ll n,m,k,size;
ll a[N];
ll cnt[N],ans[N];
void modui() {
    size=sqrt(n);
    for(ll i=1;i<=m;i++) {
        ll l,r;
        cin>>l>>r;  
        q[i].l=l;
        q[i].r=r;
        q[i].id=i;
        q[i].block=(l-1)/size+1;
    }
    sort(q+1,q+1+m);
    ll l=1,r=1;
    ll res=0;

    for(ll i=q[1].l;i<=q[1].r;i++) {
        res-=cnt[a[i]]*cnt[a[i]];
        cnt[a[i]]++;
        res+=cnt[a[i]]*cnt[a[i]];
    }
    l=q[1].l;
    r=q[1].r;
    ans[q[1].id]=res;

    for(ll i=2;i<=m;i++) {
        while(l<q[i].l) {
            res-=cnt[a[l]]*cnt[a[l]];
            cnt[a[l]]--;
            res+=cnt[a[l]]*cnt[a[l]];
            l++;
        }
        while(l>q[i].l) {
            l--;
            res-=cnt[a[l]]*cnt[a[l]];
            cnt[a[l]]++;
            res+=cnt[a[l]]*cnt[a[l]];
        }
        while(r<q[i].r) {
            r++;
            res-=cnt[a[r]]*cnt[a[r]];
            cnt[a[r]]++;
            res+=cnt[a[r]]*cnt[a[r]];
        }
        while(r>q[i].r) {
            res-=cnt[a[r]]*cnt[a[r]];
            cnt[a[r]]--;
            res+=cnt[a[r]]*cnt[a[r]];
            r--;
        }
        l=q[i].l;
        r=q[i].r;
        ans[q[i].id]=res;
    }
}
void solve() {
    cin>>n>>m>>k;
    for(ll i=1;i<=n;i++) cin>>a[i];
    modui();
    for(ll i=1;i<=m;i++) {
        cout<<ans[i]<<endl;
    }

}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll T=1;
    //cin>>T;
    while(T--) {

        solve();
    }
    return 0;
}

SPOJ DQUERY - D-query https://www.spoj.com/problems/DQUERY/

// Problem: D-query
// Contest: SPOJ - Classical
// URL: https://www.spoj.com/problems/DQUERY/
// Memory Limit: 1536 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f; 
ll n,m;
ll a[N],ans[N],cnt[N];
ll size;
ll res=0;
struct Query{
    ll l,r,id,block;
    bool operator  <(const Query& p) const{
        if(block==p.block) 
          return r<p.r;
        return block<p.block;
    }
}q[N];
void add(ll i) {
    cnt[a[i]]++;
    if(cnt[a[i]]==1) res++;
}
void del(ll i) {
    cnt[a[i]]--;
    if(cnt[a[i]]==0) res--;
}
void modui() {
    size=sqrt(n);
    for(ll i=1;i<=m;i++) {
        ll l,r;
        cin>>l>>r;
        q[i].l=l;
        q[i].r=r;
        q[i].id=i;
        q[i].block=(l-1)/size+1;
    }
    sort(q+1,q+1+m);

    ll l=1,r=0;

    for(ll i=1;i<=m;i++) {
        while(l<q[i].l) {
            del(l++);
        }
        while(l>q[i].l) {
            add(--l);
        }
        while(r<q[i].r) {
            add(++r);
        }
        while(r>q[i].r) {
            del(r--);
        }
        ans[q[i].id]=res;
    }

}
void solve() {
    cin>>n;
    for(ll i=1;i<=n;i++) 
        cin>>a[i];
    cin>>m;
    modui();

    for(ll i=1;i<=m;i++) {
        cout<<ans[i]<<endl;
    }




}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll T=1;
    //cin>>T;
    while(T--) {

        solve();
    }
    return 0;
}