莫队学习

处理什么样的问题：

给定一个长度为N的数列 以及q个询问 每次询问一个区间的某一类值 暴力做法为（q*n*n）或（q*n），会超时。

核心思想：离线分块。可以将q次查询按照双关键字排序。将数列分成sqrt(n)块每块长度为sqrt(n)。

排序一般是按照双关键字排序 第一关键字是左边界所在的块 第二关键字是右边界。

排序后时间复杂度将优化到nsqrt(n)

为什么呢？

证明过程：

按照上面这样排序可以优化常数

核心代码：

for(int i=1,l=1,r=0;i<=q;i++){
    while(l<b[i].l)sub(a[l++]);
    while(l>b[i].l)add(a[--l]);
    while(r<b[i].r)add(a[++r]);
    while(r>b[i].r)sub(a[r--]);
}

那如果数列中有修改怎么办呢 那就要用到带修莫队。

带修莫队模版题

设计到带修莫队 就必须搞一个时间戳 然后双关键字排序变成三关键字排序。

同时块的大小变成pow(n,0.66)

先按照不带修的莫队查询好 再通过时间搓的变化来计算改变了之后的贡献

新加代码如下：

                while(x<query[i].tim){
			int p=rem[++x].x;
			//要变大
			if(p<=r and p>=l){
				del(a[p]),add(rem[x].y);
			}
			swap(a[p],rem[x].y);
		}
		while(x>query[i].tim){
			int p=rem[x].x;
			//要变小
			if(p<=r and p>=l){
				del(a[p]),add(rem[x].y);
			}
			swap(a[p],rem[x--].y);
		}