题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3781
一眼莫队
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<bits/stdc++.h> #define maxn 50050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int l,r; int id; }q[maxn]; int n,m,k,block,ans; int a[maxn],belong[maxn],num[maxn]; int Ans[maxn]; bool operator < (node x,node y){ if(belong[x.l]==belong[y.l])return x.r<y.r; return belong[x.l]<belong[y.l]; } inline void init(){ n=rd(),m=rd(),k=rd(); block=(int)sqrt(k); generate(a+1,a+n+1,rd); for(int i=1; i<=m; i++)q[i].l=rd(),q[i].r=rd(),q[i].id=i; for(int i=1; i<=n; i++)belong[i]=i/block; sort(q+1,q+m+1); } inline void add(int x){ ans-=num[x]*num[x]; num[x]++; ans+=num[x]*num[x]; } inline void del(int x){ ans-=num[x]*num[x]; num[x]--; ans+=num[x]*num[x]; } inline void work(){ int l=1,r=1; add(a[1]); for(int i=1; i<=m; i++){ while(r<q[i].r)add(a[++r]); while(l>q[i].l)add(a[--l]); while(l<q[i].l)del(a[l++]); while(r>q[i].r)del(a[r--]); Ans[q[i].id]=ans; } for(int i=1; i<=m; i++)printf("%d\n",Ans[i]); } int main(){ init(); work(); return 0; } |