小B的询问 题解

• http://www.lydsy.com/JudgeOnline/problem.php?id=3781
• https://www.luogu.com.cn/problem/P2709

修改一下莫队的增加与修改即可。

#include <bits/stdc++.h>
using namespace std;
int n,a[50010],m,p;
int L=1,R=0,bl;
struct node {
	int l,r,num;
} q[200010];
bool cmp(node a,node b) {
	return (a.l/bl)==(b.l/bl)?a.r<b.r:(a.l/bl)<(b.l/bl);
}
int cnt[1000010],sum;
void add(int x) {
	cnt[x]++;
	sum+=cnt[x]*cnt[x]-(cnt[x]-1)*(cnt[x]-1);
}
void del(int x) {
	cnt[x]--;
	sum-=(cnt[x]+1)*(cnt[x]+1)-cnt[x]*cnt[x];
}//如上为莫队的修改操作，其实就改了一点点
int ans[200010];
int main() {
	scanf("%d %d %*d",&n,&m);
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	//scanf("%d",&m);
	for(int i=1;i<=m;i++)
	    scanf("%d %d",&q[i].l,&q[i].r),q[i].num=i;
	bl=sqrt(n);
	//printf("%d\n",bl);
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=m;i++) {
		//printf("now do %d\n",q[i].num);
		while(R<q[i].r) add(a[++R]);
		while(R>q[i].r) del(a[R--]);
		while(L<q[i].l) del(a[L++]);
		while(L>q[i].l) add(a[--L]);
		ans[q[i].num]=sum;
	}
	for(int i=1;i<=m;i++)
	    printf("%d\n",ans[i]);
	return 0;
}

小B的询问 题解

原文：https://www.cnblogs.com/lajiccf/p/12903942.html