二维莫队解题报告
我写的莫队教程
其实这是一道bzoj上的题（bzoj2639，貌似是权限题，反正我看不了），在YALI做模拟赛的时候遇到了.
然后在网上查到了几篇关于这道题的博客，都和我的做法略有不同...
题目大意
给你一个 \(r*c\) 的矩阵，每个点有一个颜色， \(m\) 个询问，每次询问一个子矩阵内，每种颜色出现次数的平方和。
\(r,c\le 200,m\le 100000\)
做法简述
首先我们要明白，莫队究竟在干什么。
莫队其实就是几个指针在那跳来跳去，每跳一步都需要一定的时间，通过对询问排序使得指针跳的总次数尽量小。
所以，这题中询问为 \((x_1,y_1,x_2,y_2)\) ，也就是四个指针在那跳，分别分块再排序就可以了，即：
//为避免和cmath库中的y0y1重名，下文中代码内的x1,y1,x2,y2都用x,y,xx,yy代替
struct Query
{
int x,y,xx,yy,id;
bool operator<(Query& b)
{
return x/B==b.x/B?(y/B==b.y/B?(xx/B==b.xx/B?yy答案更新
一般的莫队都是 \(O(1)\) 更新答案的，然而这题是 \(O(n)\) （用 \(n\) 代表 \(r,c\) ） 更新。
移动指针的时候，把一排一起修改。
需要注意的是，8个while的顺序如果排列不当在某些情况下会导致答案出错，所以最好是将所有add都放在del前面（实际上有多种排列顺序都可以在不进行“反操作”的情况下保证答案正确，所有add放在del前面只是其中一种），或者是对“反区间”进行“反操作”。
所谓“反区间”，如：修改 \(x_1\) 指针时，本应进行add操作，而此时\(y_1>y_2+1\)，那么就要将 \((y_2,y_1)\) 这个开区间内的所有点进行del。
while的排列顺序得当可以使“反区间”不可能出现。
“反操作”参考代码：
while (xq[i].xx)
{
for (j=y;j<=yy;++j)
{
del(a[xx][j]);
}
for (j=yy+1;jq[i].yy)
{
for (j=x;j<=xx;++j)
{
del(a[j][yy]);
}
for (j=xx+1;jq[i].x)
{
--x;
for (j=y;j<=yy;++j)
{
add(a[x][j]);
}
for (j=yy+1;jq[i].y)
{
--y;
for (j=x;j<=xx;++j)
{
add(a[j][y]);
}
for (j=xx+1;j 分块大小
具体计算清楚非常复杂，这里只是估算一下.
\(x_1\) 指针的移动次数为 \(O(mB)\)，\(y_2\) 指针的移动次数渐进复杂度中含有 \(O\left(\frac{n^4}{B^3}\right)\)，取 \(mB=\frac{n^4}{B^3}\)，得到 \(B=nm^{-\frac{1}{4}}\)
总时间复杂度为 \(O(mlogm+n^2m^{\frac{3}{4}})\)
反正这样的分块大小实测比 \(\sqrt{n}\) 优秀...有兴趣的话可以严谨地算一算（如果发现我这个估算有问题可以直接在这篇博客下评论）
初始子矩阵
任意一个空矩阵就可以了，如 \(x_1=y_1=1,x_2=y_2=0\)
参考代码
#include
#include
#include
#include
using namespace std;
const int N=210;
const int M=100010;
void add(int x);
void del(int x);
int r,c,m,B,a[N][N],lsh[N*N],tot,cnt[N*N],ans,out[M];
struct Query
{
int x,y,xx,yy,id;
bool operator<(Query& b)
{
return x/B==b.x/B?(y/B==b.y/B?(xx/B==b.xx/B?yy>r>>c>>m;
B=pow(r*c,0.5)/pow(m,0.25)+1.0;
for (i=1;i<=r;++i)
{
for (j=1;j<=c;++j)
{
cin>>a[i][j];
lsh[tot++]=a[i][j]; //这题要离散化
}
}
sort(lsh,lsh+tot);
tot=unique(lsh,lsh+tot)-lsh;
for (i=1;i<=r;++i)
{
for (j=1;j<=c;++j)
{
a[i][j]=lower_bound(lsh,lsh+tot,a[i][j])-lsh;
}
}
for (i=0;i>q[i].x>>q[i].y>>q[i].xx>>q[i].yy;
q[i].id=i;
}
sort(q,q+m);
for (i=0;iq[i].x)
{
--x;
for (j=y;j<=yy;++j)
{
add(a[x][j]);
}
}
while (xxq[i].y)
{
--y;
for (j=x;j<=xx;++j)
{
add(a[j][y]);
}
}
while (yyq[i].xx)
{
for (j=y;j<=yy;++j)
{
del(a[xx][j]);
}
--xx;
}
while (yq[i].yy)
{
for (j=x;j<=xx;++j)
{
del(a[j][yy]);
}
--yy;
}
out[q[i].id]=ans;
}
for (i=0;i