P2709 小B的询问
莫队算法,弄两个指针乱搞即可
这应该是基础莫队了吧
$x^2$可以拆成$((x-1)+1)^2$,也就是$(x-1)^2+1^2+2 imes (x-1)$,那么如果一个数字出现的次数修改$-1$,那么$ans-=1+2 imes (sum[a[pos]]-1)$,$sum[a[pos]]$表示出现在$pos$位置上的数出现的次数。
反之同理。。。
#include<bits/stdc++.h> #define N 500000 using namespace std; int n,m,k,bl,v[N],ans,sum[N]; struct node{ int l,r,id,an; }e[N]; bool cmp(node A,node B){ return A.l/bl==B.l/bl ? A.r<B.r : A.l<B.l; } bool ccmp(node A,node B){ return A.id<B.id; } void remove(int x){ ans-=1+2*(sum[v[x]]-1),sum[v[x]]--; } void insert(int x){ ans+=1+2*(sum[v[x]]),sum[v[x]]++; } int main() { scanf("%d%d%d",&n,&m,&k); bl=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1;i<=m;i++) scanf("%d%d",&e[i].l,&e[i].r),e[i].id=i; sort(e+1,e+1+m,cmp); int curL=0,curR=0; for(int i=1;i<=m;i++){ int L=e[i].l,R=e[i].r; while(curL<L) remove(curL++); while(curL>L) insert(--curL); while(curR>R) remove(curR--); while(curR<R) insert(++curR); e[i].an=ans; } sort(e+1,e+1+m,ccmp); for(int i=1;i<=m;i++) printf("%d ",e[i].an-1); return 0; }