莫队
莫队
两只小手跳来跳去
众所周知，莫队算法是由莫涛大神总结的又短又快的离线暴力维护区间操作的算法。
因起简短的框架，简单好记的板子和优秀的时间复杂度而闻名。
莫队题单
普通莫队
基本思路
普通莫队就是最普通的莫队。
举个简单的例子：
对于给定的数列，k 次询问，每次输出区间 [l,r] 的区间和。
显然啊，这题可以直接前缀和。但既然是学莫队，那就强制用莫队做。
如果现在知道 \([2,5]\) 的区间和，怎么求区间 \([2,6]\) 的区间和？
显然，直接用前者 \(+a_6\) 就可以了。
莫队就是这样。莫队的核心就是在 \(O(1)\) 的时间里从状态 \([l,r]\) 转移到状态 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 其中之一。
就是开头说的两只小手跳来跳去。
等等。
如果将方括号换成圆括号的话……
那不就是从状态 \((l,r)\) 转移到状态 \((l-1,r),(l+1,r),(l,r-1),(l,r+1)\) 嘛。
那不就是以 \(l\) 为横坐标，\(r\) 为纵坐标的平面直角坐标系上的点吗？
就是这样：
这就是莫队的二维理解。
举个例子：
比如我们要维护 \([1,4],[2,6],[3,5],[5,6]\) 四个区间，就相当于是坐标系上的 \((1,4),(2,6),(3,5),(5,6)\) 四个点。也就是：
而从一个点去到另一个点的花费就是两点的曼哈顿距离。
显然，我们要在较短的时间里完成所有的任务，那么就是要经历所有的点，且费用较小。
如果是最优，那显然是，不过既然我们是暴力，那显然不用最优。
接下来思考：
如果按照询问顺序进行回答的话……
显然不行，比如我给你这样几个点：
\((1,2),(99999,100000),(1,2),(99999,100000)\cdots\)
那么你每次移动都要跑整个序列。累死两只小手
如果将所有的点储存下来，然后按左端点排序之后再依次遍历的话……
就是这样：
对于上边的的好像可以？
\((1,2),(1,2)\cdots(99999,100000),(99999,100000)\cdots\)
确实。
但还是不行。
为啥？
比如我给你这样的几个点：
\((1,10^5),(2,2),(3,10^5),(4,4)\cdots\)
上上下下来来回回累死两个小手
不过这给我们了一个启示：不同的询问顺序，询问总时间也是不同的。
所以要对询问顺序进行优化。
以上便是莫队的前置知识。
至于优化方案……
分块！
将所有的点按照块长为 \(\sqrt n\) 进行分块，块外左端点块递增，块内右端点递增。
那么上例中每个块中就是递增的，逐步上跳总比来回跑快吧。
代码处理
先完善一下上述题面：
题面描述：
给定一个长度为 n 的数列，有 m 询问，每次询问输出区间 \([l,r]\) 中各个元素的和。
输入格式：
第一行两个整数 n,m，含义如上。
第二行 n 个数，表示原数列。
接下来 m 行，每行两个整数 [l,r]，表示查找的区间。
数据范围：
\(n,m<10^5\)
首先进行分块
len=sqrt(n);
for(int i=1;i<=n;i++)
a[i]=re(),bel[i]=i/len;
然后我们要将所有的询问储存下来
for(int i=1;i<=m;i++)
{
int l=re(),r=re();
h.push_back((Query){l,r,i});
}
sort(h.begin(),h.end());
然后两只小手跳来跳去。
int il=1,ir=0;
for(int i=0;ils.le)insert(--il);
while(ills.ri)remove(ir--);
ans_[ls.id]=ans;
}
这里需要注意的是加减顺序和 insert,remove 的相对关系。
insert 是先移动再插入，remove 是先删除再移动。
左手是向右删除，向左插入；右手是向左删除，向右插入。
而 insert 和 remove 函数就要根据题目进行推导（就像递推式）
在这个题中就是这样：
void insert(int i)
{
ans+=a[i];
}
void remove(int i)
{
ans-=a[i];
}
再优化
- 手打快读快写
比 scanf 快点。
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
void wr(int s)
{
if(s<0)putchar('-'),s=-s;
if(s>9)wr(s/10);
putchar(s%10+48);
}
当然也有比我的更快的，这个只是我习惯的。
- 奇偶优化
别人说奇偶优化是玄学，可我感觉奇偶优化是艺术。
顾名思义，奇偶优化就是按照块的奇偶性进行优化。将奇数块内部按照右端点递增，偶数块内部按照右端点递减，块外按左端点递增进行排序。
（奇数块递减，偶数块递增也是可以的。）
刚刚是块内部逐步上跳，但是块与块之间是直接下来的，花费较大。但这时我们是逐步上跳，再逐步下跳。花费就更小了。
operator 就这样打：
bool operator <(const Query &b)const
{
return (bel[le]==bel[b.le])?((bel[le]&1)?(rib.ri)):(le - 常数优化
while(il>ls.le)insert(--il);
while(ills.ri)remove(ir--);
void insert(int i)
{
ans+=a[i];
}
void remove(int i)
{
ans-=a[i];
}
压缩成
while(il>ls.le)ans+=a[--il];
while(ills.ri)ans-=a[ir--];
例题
假设新加进来的袜子的颜色为 c，且现在颜色为 c 的袜子有 t 个。
根据排列组合知识，加入之前拿到相同颜色袜子的组合有 \(C_t^2\) 种，加入之后为 \(C_{t+1}^2\)，则应该有：
\[\begin{aligned}ans&=ans-C_t^2+C_{t+1}^2\\&=ans-\dfrac{t(t-1)}{2}+\dfrac{t(t+1)}{2}\\&=ans+t\end{aligned} \]同理可知，删除时有 \(ans=ans-(t-1)\)。
则 insert 和 remove 就好写了：
inline void insert(int i)
{
ans+=tong[a[i]]++;
}
inline void remove(int i)
{
ans-=--tong[a[i]];
}
带修莫队
通过上面叙述可知，莫队强制离线算法。
那么对于带修莫队要怎样实现呢？
回想莫队的二维理解，我们可以再引入一条时间轴，然后在分块排序的时候按照以下原则进行排序：
- 左端点不同块：左端点递增。
- 左端点同块，右端点不同块：右端点递增。
- 左右端点均不同块：修改时间递增。
然后就相当于是从状态 \([l,r,t]\) 转移到状态 \([l,r,t-1],[l,r,t+1],[l-1,r,t],[l+1,r,t],[l,r-1,t],[l,r+1,t]\) 之一。
而且对于要更改的点，如果在查询的区间内，还要顺带着将统计的答案更新。
例题
Code
#include
#include
#include
#include
using namespace std;
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
void wr(int s)
{
if(s<0)putchar('-'),s=-s;
if(s>9)wr(s/10);
putchar(s%10+48);
}
const int inf=1e6+7;
int n,m,len,ans;
int a[inf],tong[inf],bel[inf];
int ans_[inf];
int cntq,cntr;
struct Query{
int le,ri,id,pos;
bool up;int val;
Query(int le=0,int ri=0,int id=0,int pos=0,bool up=0,int val=0):
le(le),ri(ri),id(id),pos(pos),up(up),val(val){}
bool operator <(const Query &b)const
{
return (bel[le]==bel[b.le])?((bel[ri]==bel[b.ri])?(idh;
struct Change{
int pos,val;
}c[inf];
void insert(int i)
{
if(tong[a[i]]==0)ans++;
tong[a[i]]++;
}
void remove(int i)
{
if(tong[a[i]]==1)ans--;
tong[a[i]]--;
}
int main()
{
n=re();m=re();
len=pow(n,2.0/3);
for(int i=1;i<=n;i++)
a[i]=re(),bel[i]=i/len;
for(int i=1;i<=m;i++)
{
char op[10]="";scanf("%s",op);
int l=re(),r=re();Query ls(0);
if(op[0]=='Q')
{
ls.le=l,ls.ri=r;
ls.id=cntr,ls.pos=++cntq;
h.push_back(ls);
}
else c[++cntr]=(Change){l,r};
}
sort(h.begin(),h.end());
int il=1,ir=0,nowup=0;
for(int i=0;ils.id)
{
if(il<=c[nowup].pos&&c[nowup].pos<=ir)
{
tong[a[c[nowup].pos]]--;
if(tong[a[c[nowup].pos]]==0)ans--;
if(tong[c[nowup].val]==0)ans++;
tong[c[nowup].val]++;
}
swap(a[c[nowup].pos],c[nowup].val);
nowup--;
}
while(il>ls.le)insert(--il);
while(ills.ri)remove(ir--);
ans_[ls.pos]=ans;
}
for(int i=1;i<=cntq;i++)
wr(ans_[i]),putchar('\n');
return 0;
}