莫队

用途

问题存在可从区间 \(l,r\) \(O(1)\) 转移到 \(l+1,r\) \(or\) \(l-1,r\) \(or\) \(l,r+1\) \(or\) \(l,r-1\)　的时候就可以使用莫队。

实现

两个指针记录　\(l,r\) ,将其排序,然后\(O(1)\) 移动计算贡献即可,复杂度整体为 \(O(n \sqrt n)\) 。

排序

排序部分如下:

bool cmp(node a,node b){
	if(belong[a.l]==belong[b.l]) return a.r<b.r;
	return a.l<b.l;
}

同一个块看 \(r\) 否则看 \(l\) 。

优化:奇偶性排序 。

计算贡献

		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);

\(add\) 和 \(del\) 视情况而定 。