最简单的莫队入门，洛谷数据有加强，吸氧+读优莽过去 注释见代码
//各种优化+O2终于过了 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; template<class T>inline void read(T &re) { char ch; while((ch=getchar())<'0'||ch>'9'); re=ch-48; while((ch=getchar())>='0'&&ch<='9') re=(re<<3)+(re<<1)+ch-48; } struct node{ int l;//询问左右端点 int r; int id; int belong; }mo[maxn*4]; int block; int s[maxn]; long long ans[maxn];//离线保存答案 int cnt[maxn];//数列中每个数出现的次数 long long sum; int n,m,k; int l,r;//两个指针 // 莫队算法首先将整个序列分成√n个块（同样，只是概念上分的块，实际上我们并不需要严格存储块），接着将每个询问按照块序号排序（一样则按照右端点排序）。 bool cmp(node a,node b){ return a.r<b.r?a.belong==b.belong:a.belong<b.belong; } inline void add(int x){ cnt[s[x]]++; sum+=2*cnt[s[x]]-1; } inline void del(int x){ cnt[s[x]]--; sum-=2*cnt[s[x]]+1; } int main(){ read(n); read(m); read(k); block=sqrt(n); for(register int i=1;i<=n;i++){ read(s[i]); } for(register int i=1;i<=m;i++){ read(mo[i].l);read(mo[i].r); mo[i].id=i; mo[i].belong=(mo[i].l-1)/block+1; } sort(mo+1,mo+1+m,cmp); l=1; r=0; //两个指针的初始位置，类比于队列 for(register int i=1;i<=m;i++){ while(l<mo[i].l) del(l++);//迷之指针 while(l>mo[i].l) add(--l); while(r>mo[i].r) del(r--); while(r<mo[i].r) add(++r); ans[mo[i].id]=sum; } for(register int i=1;i<=m;i++){ printf("%lld ",ans[i]); } return 0; }