带修莫队

众所周知，普通莫队是不支持修改的，因为我们为了得到更优的时间复杂度，需要将每次询问离线下来，打乱顺序。

不过我们也可以通过加上一维时间维强行让它支持修改，这里的时间维在题目意义上就是需要进行的修改次数。

主要思想

原本我们的转移只有四种，以当前为 \(\left[l,r\right]\) 为例，我们可以 \(\mathcal{O(1)}\) 扩展到：

\(\left[l-1,r\right]\)
\(\left[l+1,r\right]\)
\(\left[l,r-1\right]\)
\(\left[l,r+1\right]\)

若添加上一维时间，那么我们需要进行六种转移：

\(\left[l-1,r,time\right]\)
\(\left[l+1,r,time\right]\)
\(\left[l,r-1,time\right]\)
\(\left[l,r+1,time\right]\)
\(\left[l,r,time-1\right]\)
\(\left[l,r,time+1\right]\)

只是多了种转移方式，并不影响我们转移的复杂度。

离线询问排序的原则，以左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字升序排列。

块长选定与时间复杂度

块长方面，通常取 \(\mathcal{n^{\frac{2}{3}}}\)，最终复杂度为 \(\mathcal{O(n^{\frac{5}{3}})}\)。

关于最优块长的分析：

摘自 OI-wiki。

实现

以 P1903 数颜色/ 维护队列为例。

带修莫队板子题，思路同上，这里主要讲一下两个时间维的转移。

思路很简单，当查询到某次询问 \(q\) 时，若当前时间小于该次时间，则进行转移。若某次更改的点恰好在当前区间范围内，则进行更改操作，更改操作可以视为一次删除和一次添加，操作完成后为了方便之后再回退回去，我们交换删除的元素和更新的元素。

操作分离：

for(int i=1;i<=m;i++)
{
	char op;int x,y;
	cin>>op>>x>>y;
	if(op=='Q')
		q[++qcnt].id=qcnt,q[qcnt].time=rcnt,
		q[qcnt].x=x,q[qcnt].y=y;
	else
		r[++rcnt].p=x,r[rcnt].x=y;
}

转移部分：

void add(int x)
{
	if(!mp[x]) anss++;
	mp[x]++;
}
void del(int x)
{
	mp[x]--;
	if(!mp[x]) anss--;
}
int main()
{
	/*code*/
	int L=1,R=0,tim=0;
	for(int i=1;i<=qcnt;i++)
	{// 转移原则：先扩大后缩小
		while(L>q[i].x) add(a[--L]);
		while(R<q[i].y) add(a[++R]);
		while(L<q[i].x) del(a[L++]);
		while(R>q[i].y) del(a[R--]);
		while(tim<q[i].time)
		{
			tim++;
			if(L<=r[tim].p&&r[tim].p<=R)
				add(r[tim].x),del(a[r[tim].p]);
			swap(a[r[tim].p],r[rim].x);
		}
		while(tim>q[i].time)
		{
			if(L<=r[tim].p&&r[tim].p<=R)
				add(r[tim].x),del(a[r[tim].p]);
			swap(a[r[tim].p],r[tim].x);
			tim--;
		}
		ans[q[i].id]=anss;
	}
}

二维莫队

普通的莫队算法处理的是序列上的问题，如果我们将它扩展成一个平面，使得转移时可以有四个方向选择，就得到了二维莫队。

二维莫队的转移操作每次移动指针要操作一行或一列的数，具体实现方式与普通的一维莫队类似。

块长选定与时间复杂度

摘自 OI-wiki。

简而言之，设矩阵大小为 \(S\)，询问次数为 \(q\)，我们的块长通常选定为 \(\frac{\sqrt S}{q^{\frac{1}{4}}}\)，这样算得的结果若小于 1，我们直接为其赋值为 1 即可。

最终，在求解部分的时间复杂度是 \(\mathcal{O(S·q^{\frac{3}{4}})}\)，总时间复杂度为 \(\mathcal{O(S·q^{\frac{3}{4}}+q\log q)}\)。

实现

例题：给定一个大小为 \(n\times m\) 的矩阵，接着给出 \(q\) 个询问，每次询问一个子矩阵的权值，权值定义为：若一元素在某矩阵出现了 \(k\) 次，那么它的贡献就为 \(k^2\)。

结构体定义：

给定一个矩形的左上角坐标和右下角坐标，我们按左上角横坐标、左上角纵坐标、右下角横坐标、右下角纵坐标所属块的顺序升序排列。

struct Que
{
	int lx,ly,rx,ry,id;
	bool operator<(const Que &A)const
	{
		if(lx/B!=A.lx/B) return lx<A.lx;
		if(ly/B!=A.ly/B) return ly<A.ly;
		if(rx/B!=A.rx/B) return rx<A.rx;
		return ry<A.ry;
	}
}que[N];

转移部分：

对于行与列，我们用不同的函数

int a[N][N];// 原矩阵
int cnt[N];// 某数出现的
void mdfline(int id,int val,int u,int v)
{// 增加/删除某一行
	for(int i=u;i<=v;i++)
		anss-=1ll*cnt[a[id][i]]*cnt[a[id][i]],
		cnt[a[id][i]]+=val,
		anss+=1ll*cnt[a[id][i]]*cnt[a[id][i]];
}
void mdfcolumn(int id,int val,int u,int v)
{
	for(int i=u;i<=v;i++)
		anss-=1ll*cnt[a[i][id]]*cnt[a[i][id]],
		cnt[a[i][id]]+=val,
		anss+=1ll*cnt[a[i][id]]*cnt[a[i][id]];
}
int main()
{
	/*code*/
	B=pow(n*m,0.5)/pow(q,0.25);
	if(B<1) B=1;
	sort(que+1,que+1+q);
	int lx=1,ly=1,rx=0,ry=0;
	for(int i=1;i<=q;i++)
	{
		while(lx>que[i].lx) mdfline(--lx,1,ly,ry);
		while(rx<que[i].rx) mdfline(++rx,1,ly,ry);
		while(ly>que[i].ly) mdfcolumn(--ly,1,lx,rx);
		while(ry<que[i].ry) mdfcolumn(++ry,1,lx,rx);
		while(lx<que[i].lx) mdfline(lx++,-1,ly,ry);
		while(rx>que[i].rx) mdfline(rx--,-1,ly,ry);
		while(ly<que[i].ly) mdfcolumn(ly++,-1,lx,rx);
		while(ry>que[i].ry) mdfcolumn(ry--,-1,lx,rx);
		ans[que[i].id]=anss;
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}