莫队模板：注意求和时 n^2 -->(n+1)^2 多2*n+1
以此类推！！！
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define ll long long #define re register const int N=50005; void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } struct note { int l,r,pos,id; bool operator < (const note &x) const { if(x.pos==pos) return r>x.r; else return pos>x.pos; } }a[N]; int b[N]; ll cnt[N],ANS[N]; int main() { int n,m,k; read(n); read(m); read(k); int siz=sqrt(n); for(re int i=1;i<=n;i++) read(b[i]); for(re int i=1;i<=m;i++) { read(a[i].l); read(a[i].r); a[i].id=i; a[i].pos=(a[i].l-1)/siz+1; } sort(a+1,a+1+n); int l=n+1,r=n,ans=0; for(re int i=1;i<=m;i++) { while(l>a[i].l) l--,ans=ans+2*cnt[b[l]]+1,cnt[b[l]]++; while(r<a[i].r) r++,ans=ans+2*cnt[b[r]]+1,cnt[b[r]]++; while(l<a[i].l) ans=ans-2*cnt[b[l]]+1,cnt[b[l]]--,l++; while(r>a[i].r) ans=ans-2*cnt[b[r]]+1,cnt[b[r]]--,r--; ANS[a[i].id]=ans; } for(re int i=1;i<=m;i++) printf("%lld ",ANS[i]); return 0; }