P2709

莫队

特点

是一种优雅的暴力

解决大部分区间离线问题的离线算法

主要思想为分块，将 \(n^2\) 降为 \(n \sqrt{n}\)

题目关键词包含\(n,m,k\),并有多个询问\(L_i,R_i\)，求区间内的...

思想

相当于有两个指针\(L,R\)，若当前询问的区间为\(l[i],r[i]\)那么会分别将 \(L,R\) 向\(l[i],r[i]\)的方向移动，并在移动时做出与题目要求相关的操作

模板

int sz = sqrt(n);//每一块的大小为根号n
for(int i=1;i<=n;i++)
  belong[i] = i / sz; //将每一个位置划分到对应的块里面去
sort();//先按照每次询问的左端点所在的块号排序，如果两个区间左端点所在的块相同，那么按照右端点小的在前
int L = 1,R = 0;//初始化两个指针，R = 0，是为了能将第一个添加进去
for(int i=1;i<=m;i++)
{
	while(q[i].l < L) add(--L);
	while(q[i].l > L) sub(L++);
	while(q[i].r < R) sub(R--);
	while(q[i].r > R) add(++R);
	ans[q[i].id] = res;//q[i].id表示原来它是第几次询问，因为要跟询问顺序保持一致，res为每次更新区间之后的答案
}

P2709 code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn = 5e4+5;
int n,m,k,a[maxn],belong[maxn],cnt[maxn];
LL res,ans[maxn];
struct range{
	int l,r,id;
}q[maxn];

bool cmp(range x,range y)
{
	return belong[x.l] == belong[y.l] ? x.r < y.r : belong[x.l] < belong[y.l];
}

void add(int x)
{
	res = res + 2 * cnt[a[x]] + 1;
	cnt[a[x]] ++;
	return ;
}

void sub(int x)
{
	res = res - 2 * cnt[a[x]] + 1;
	cnt[a[x]] --;
	return ;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	int sz = sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		belong[i] = i / sz;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q+1,q+m+1,cmp);
	int L = 1,R = 0;
	for(int i=1;i<=m;i++)
	{
		while(q[i].l < L) add(--L);
		while(q[i].l > L) sub(L++);
		while(q[i].r < R) sub(R--);
		while(q[i].r > R) add(++R);
		ans[q[i].id] = res;
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}