[题解]洛谷P2709 小B的询问

是一道莫队模板题。

分析
- 设( ext{vis[i]})表示元素( ext{i})出现的次数
- 当一个元素进入莫队时，它对答案的贡献增加。有(delta Ans=(X+1)^2-X^2=2X+1)
- 注意莫队中得到的答案是乱序的。需要一个辅助数组实现顺序输出。
注意事项
- 利用奇偶优化可以提高效率。具体来说，在排序中：
  - 两个元素( ext{X,Y})有(X.Left≠Y.left)，以( ext{Left})为第一关键字。
  - 否则讨论( ext{Left})的奇偶性，分别对( ext{Right})正序或倒序
- 使用( ext{O2})优化

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define Clean(X,K) memset(X,K,sizeof(X))
#define GC getchar()
#include <algorithm>
using namespace std ;
const int Maxn = 50005 ;
int Qread () {
	int X = 0 , F = 1;
	char C = GC ;
	while (C > '9' || C < '0') {
		if (C == '-') F = -1 ;
		C = GC ;
	}
	while (C >='0' && C <='9') {
		X = X * 10 + C - '0' ;
		C = GC ;
	}
	return X *F ;
}
int L = 1 , R = 1 , Ans[Maxn] , N , K , M , A[Maxn] , Vis[Maxn] , Now = 1;
struct Node {
	int Left , Right , Place;
};
Node B[Maxn] ;
bool Cmp (const Node &X , const Node &Y) {
	if (X.Left != Y.Left ) return X.Left < Y.Left ;
	if (X.Left & 1) return X.Right  < Y.Right  ;
	return X.Right > Y.Right ;
}
int main () {
//	freopen ("P2709.in" , "r" , stdin) ;
	N = Qread () , M = Qread () , K = Qread () ;
	for (int i = 1 ; i <= N; ++ i) A[i] = Qread () ;
	for (int i = 1 ; i <= M; ++ i) B[i].Left = Qread () , B[i].Right = Qread () , B[i].Place = i;
	std :: sort (B + 1 , B + 1 + M , Cmp) ;
	Clean (Vis , 0) ;
	Vis[A[1]] = 1 ;
	for (int i = 1 ; i <= M; ++ i) {
		while (B[i].Left > L) {
			-- Vis[A[L]] ;
			Now -= (Vis[A[L]] << 1) + 1;
			++ L ;
		}
		while (B[i].Right > R) {
			++ R ;
			Now += (Vis[A[R]] << 1) + 1;
			++ Vis[A[R]] ;
		}
		while (B[i].Right < R) {
			-- Vis[A[R]] ;
			Now -= (Vis[A[R]] << 1) + 1;
			-- R ;
		}
		Ans[B[i].Place ] = Now ;
	}
	for (int i = 1 ; i <= M; ++ i) printf ("%d
" , Ans[i]) ;
	fclose (stdin) , fclose (stdout) ;
	return 0 ;
}

[题解]洛谷P2709 小B的询问

Thanks！