普通莫队

对于询问奇偶分块

bool cmp(nd x,nd y)
{
	int lb = x.x / bl,rb = y.x / bl;
	if (lb ^ rb) return x.x < y.x; // l,r同块以l排序
	return lb & 1 ? (x.y > y.y) : (x.y < y.y); //不同则看l在什么块内
}
bool cmp(nd x,nd y){return (x.l / bl) ^ (y.l / bl) ? (x.l < y.l) : (((x.l / bl) & 1) ? x.r < y.r : x.r > y.r);}//这是另一打法

其中\(bl\)为块长，一般为\(\frac{n}{\sqrt{\frac{2}{3}m}}\)
接着即可开双指针乱移即可。

【GDKOI2014】小纪的作业题

这是一道比较模板的莫队，开个桶计次数，一个一个数加入或删除即可

\(\text{Code}\)

#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1e5 + 5,P = 1e9 + 7;
int n,m,L,R,bl,d[N];
LL ans,v[N],a[N],mi[N],as[N];

struct nd{int x,y,id;}b[N];
bool cmp(nd x,nd y)
{
	int lb = x.x / bl,rb = y.x / bl;
	if (lb ^ rb) return x.x < y.x;
	return lb & 1 ? (x.y > y.y) : (x.y < y.y);
}
void Mod(LL &x,LL y){x = (x + y >= P ? x + y - P : x + y);}
LL fpow(int x,LL y)
{
	LL res = 1;
	for (; x; x >>= 1,y = y * y % P)
		if (x & 1) res = res * y % P;
	return res;
}
void Insert(int x)
{
	LL g1 = v[a[x]],g2 = v[a[x]] * a[x] % P;
	if (!d[a[x]]) g1 = 0;
	Mod(ans,P - g1),Mod(ans,g2),d[a[x]]++,v[a[x]] = v[a[x]] * a[x] % P;
}
void Delete(int x)
{
	LL g1 = v[a[x]] * mi[a[x]] % P,g2 = v[a[x]];
	if (d[a[x]] <= 1) g1 = 0;
	Mod(ans,g1),Mod(ans,P - g2),d[a[x]]--,v[a[x]] = v[a[x]] * mi[a[x]] % P;
}
LL work(int l,int r)
{
	while (R < r) R++,Insert(R);
	while (L > l) L--,Insert(L);
	while (R > r) Delete(R),R--;
	while (L < l) Delete(L),L++;
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m),bl = n / (sqrt(2 * m / 3));
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]),mi[a[i]] = fpow(P - 2,a[i]),v[a[i]] = 1;
	for (int i = 1; i <= m; i++) scanf("%d%d",&b[i].x,&b[i].y),b[i].id = i;
 	sort(b + 1,b + 1 + m,cmp); L = 1,R = 0;
 	for (int i = 1; i <= m; i++) as[b[i].id] = work(b[i].x,b[i].y);
	for (int i = 1; i <= m; i++) printf("%lld\n",as[i]); 
}

树上莫队

就是在树上跑莫队，对于序列很好去跑莫队，那树呢？
没错，就是将树变成序列，与\(LCA\)有关的问题常常以树的欧拉序来跑莫队。