你以为莫队只能离线？莫队的在线化改造

# 写在前面 算法来源：朝田诗乃某天在文化课上发呆的时候随意YY的 前置知识：莫队（废话） ### **在阅读之前请保证你已熟练掌握以上知识，否则请先移步[[洛谷日报第48期]莫队算法初探](https://www.luogu.org/blog/codesonic/Mosalgorithm)** # 引言 先来看一题可爱的莫队题。 [[国家集训队]数颜色 / 维护队列](https://www.luogu.org/problemnew/show/P1903) 题面: >墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令： >1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 >2、 R P Col 把第P支画笔替换为颜色Col。 >为了满足墨墨的要求，你知道你需要干什么了吗？**本题强制在线** 本来这是可以用莫队轻松解决的题，可是总有毒瘤出题人把他拿去强制在线。诗乃很愤怒，于是尝试对莫队算法进行在线化改造。 ~~这辈子都不会写树套树的！~~ # 一、普通莫队的改造 回顾一下莫队算法：我们将所有询问离线排好序，然后每一次**从上一个询问区间**转移过来。 若我们要使莫队算法在线，“从上一个询问区间转移过来”变得不可行。我们需要预先处理好某些区间的答案，让这些区间成为莫队中的“上一个区间”，这些区间我们称为**特征区间**。 特征区间需要满足： 1、能用可以接受的时间复杂度**全部**处理出来 2、所有询问能用可以接受的时间复杂度由某个**特征区间**转移而来。 那么我们考虑选取一些“**特征点**”，将任意两个特征点之间的区间全部作为**特征区间**。假设每隔$d$步选取一个特征点，那么预处理复杂度为$O(n^2/d)$，每次询问复杂度为$O(d)$（左端点移动$d/2$步，右端点移动$d/2$步），随意证明$d=\sqrt{n}$为最优。这里设第$i$个特征点为$s_i$ 特征区间选取完毕后，我们需要保存特征区间的信息。包括： >1. 区间答案 >2. 莫队所需要的信息(如区间中每种颜色的出现次数)，这往往是几个数组。 对于第2个信息，直接维护显然会爆空间。由于绝大多数莫队维护的信息具有区间可减的性质（如出现次数），因此我们只需要维护区间 [$1$,$s_i$]中的信息，读取的时候进行前缀和加减一下即可。 总结一下步骤： >1. 预处理特征区间的信息 >2. 询问时由最近的特征区间转移过来 这样我们就完成了普通莫队的在线改造。（实质上是分块，只是时间复杂度多一个$1/2$的常数而已） # 二、如何支持修改？ （一）中所述算法只是一个众所周知的转化小技巧，但由于我们需要**预处理**特征区间的答案并保存，这使我们支持修改变得困难。 回顾一下带修莫队：在每次进行询问之前将修改时间改到应有的位置，改的时候顺便维护答案。 看看人家线段树是怎么干的：打一个懒标记，装作已经处理好了。 然后我们可以总结出一个算法：懒修改，不用就不修改，要用再说。 **以下所有复杂度按$d=n^{2/3}$计算，则共有$n^{1/3}$个特征点。** 当执行修改时，若要修改所有特征区间的答案将会导致复杂度跑满，在莫队这种卡常算法里是不太行的。因此我们对所有答案记录**答案的上一次更新时间**。 对于莫队中间过程信息，由于只需要修改$n^{1/3}$个值，直接修改即可。 询问时，如果当前特征区间的答案已经**过时**了(即答案的上一次更新时间小于当前时间)，那么将这个特征区间的答案更新至最新，然后再进行转移。（与带修莫队做法类似） 需要注意的是，**由于此时莫队的中间信息已是最新，所以我们要反着计算答案**（详见代码）。 时间复杂度：修改最多有$n$次，特征区间左端点最多有$n^{1/3}$个，右端点最多有$n^{1/3}$个，所以总复杂度为$O(n^{5/3})$，与带修莫队的复杂度相同，但是**不可能跑满**。 总结一下步骤： >1、预处理特征区间的信息 >2、修改时，修改莫队中间过程信息，不修改答案。 >3、询问时： >>1、更新所需特征区间的答案 >>2、由特征区间转移，计算答案 # 时空复杂度分析 对于普通莫队的改造，时间复杂度相等，空间复杂度增加$O(\sqrt{n})$，但事实上时间上比分块做法优秀（常数小一半），与莫队做法等同。 对于带修莫队的改造，时间复杂度与带修莫队相等，空间复杂度增加$O(n^{1/3})$。虽然改造后的莫队在修改中只需要往前修改不需要往后修改，但因为种种常数问题（可能是我太菜了），实际使用时时间与带修莫队基本等同。 # 模板 这是P1903的代码。如果你读懂了这份代码那么你就可以完全掌握诗乃莫队因为它实在是太简单了 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 50050; const int BLNB = 550; const int COL = 1000050; void read(int &x) { char ch; while(ch = getchar(), ch < '!'); x = ch - 48; while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; } int target[MAXN]; struct Change {int p, col, las;} change[MAXN]; int nc, n, m, mp[COL], tot, D, cnt[BLNB][MAXN*2], c[MAXN], blnm, spe[BLNB]; int CNT[MAXN*2], ans[BLNB][BLNB], ima, tim[BLNB][BLNB], id[MAXN]; //细节：我们不能直接在cnt[][]上做更改，所以需要记录一个临时的变化量数组CNT[] //变量解释：nc表示当前时间，mp[]和tot是离散化用的，D表示特征点步长，cnt[][]是预处理的莫队信息，id[]记录下标为i的特征点是第几个特征点，spe[]用于存储所有的特征点下标，ans[][]表示特征区间的答案，tim[][]记录答案的上一次更新时间，target[]表示离位置i最近的特征点坐标。 inline int getc(int sl, int sr, int p) { if(sl == 0 && sr == 0) return 0; else { if(c[sl] == p) return cnt[id[sr]][p]-cnt[id[sl]][p]+1; else return cnt[id[sr]][p]-cnt[id[sl]][p]; }//细节：端点特判一下 } //函数作用：读取区间[sl,sr]中的莫队数组信息。 inline void del(int pos, int sl, int sr) {if((--CNT[c[pos]])+getc(sl, sr, c[pos]) == 0) --ima;} inline void add(int pos, int sl, int sr) {if((++CNT[c[pos]])+getc(sl, sr, c[pos]) == 1) ++ima;} int main() { read(n); read(m); D = pow(n, 2.0/3);//带修莫队的块大小 for(int i = 1; i <= n; ++i) { read(c[i]); if(!mp[c[i]]) c[i] = mp[c[i]] = ++tot; else c[i] = mp[c[i]]; } int tmp = 1; spe[blnm=1]=1; id[1] = 1; for(int i = 1; i <= n; ++i) { if(i - tmp == D) tmp = i, spe[++blnm] = i, id[i] = blnm; target[i] = tmp; }//预处理特征点以及每个点对应的离它最近的特征点 int p = 1; for(int i = 1; i <= n; ++i) { ++CNT[c[i]]; if(i == spe[p]) { for(int j = 1; j <= n; ++j) cnt[p][j] = CNT[j]; ++p; } }//预处理莫队所需信息 for(int i = 1; i <= blnm; ++i) { int p = i + 1; ima = 0; memset(CNT, 0, sizeof CNT); for(int j = spe[i]; j <= n; ++j) { if((++CNT[c[j]]) == 1) ++ima; if(j == spe[p]) { ans[i][p] = ima; ++p; } } }//预处理特征区间答案 memset(CNT, 0, sizeof CNT); while(m--) { char opt; int l, r; ima = 0; while(opt = getchar(), opt != 'Q' && opt != 'R'); read(l); read(r); if(opt == 'R') { change[++nc].p = l; if(!mp[r]) r = mp[r] = ++tot; else r = mp[r]; change[nc].col = r; change[nc].las = c[l]; int p = blnm; for(; spe[p] >= l; --p) --cnt[p][c[l]], ++cnt[p][r];//修改中间过程的信息 c[l] = r; } else { int sl = target[l], sr = target[r]; int SL = sl, SR = sr; //sl、sr表示所需特征区间的左右端点。 if(sl == sr) { for(int i = l; i <= r; ++i) if(++CNT[c[i]] == 1) ++ima; printf("%d\n", ima);//细节：区间左右端点所属特征点相同，暴力计算 for(int i = l; i <= r; ++i) --CNT[c[i]]; //临时数组还原 } else { for(int t = nc; t > tim[id[sl]][id[sr]]; --t) { if(sl <= change[t].p && change[t].p <= sr) { if(++CNT[change[t].las]+getc(sl, sr, change[t].las) == 1) --ans[id[sl]][id[sr]]; if(--CNT[change[t].col]+getc(sl, sr, change[t].col) == 0) ++ans[id[sl]][id[sr]]; //反向计算答案，即把原来带修莫队的东西反过来写，详情可以参考题解里普通带修莫队的修改方式做对照。 } } for(int t = nc; t > tim[id[sl]][id[sr]]; --t) if(sl <= change[t].p && change[t].p <= sr) {--CNT[change[t].las]; ++CNT[change[t].col];} //临时数组还原 tim[id[sl]][id[sr]] = nc; ima = ans[id[sl]][id[sr]]; while(sl < l) del(sl++, SL, SR); while(sl > l) add(--sl, SL, SR); while(sr < r) add(++sr, SL, SR); while(sr > r) del(sr--, SL, SR); //可爱的四句莫队 printf("%d\n", ima); while(SL < l) add(SL++, 0, 0); while(SL > l) del(--SL, 0, 0); while(SR < r) del(++SR, 0, 0); while(SR > r) add(SR--, 0, 0); //临时数组还原 } } } } //看似有点长其实有一半代码都在做临时数组还原（清零）。如果题目时间卡得不是很紧的话大可以用memset()来代替。 ``` # 用途 主要用于把莫队题拿来强制在线逼你用树套树解决的恶心题目的骗分（不要问我经历了什么，没错就是有人把例题拿来强制在线恶心我） **使用前提：维护的数据具有区间可减性，或可以由前缀和用某种方式推导得出区间信息** 若不满足使用前提，你可以使用$vector$对于每个左端点记录信息的变化时间和变化之后的值，用可持久化思想解决。由于这种方法在空间和时间上都极其劣（时间增加$O(\sqrt{logn})$，空间增加$O(\sqrt{nlogn})$），在这里不再赘述。（其实这是诗乃一开始的改造思路） 如果你觉得它没有什么卵用的话，给一题思考题：[【模板】诗乃莫队](https://www.luogu.org/problemnew/show/T72834) # 写在最后 如果你愿意的话，可以把这种算法叫做诗乃莫队。 （我相信各路julao早已自己yy出这种简单的算法了，但由于之前似乎没有人提出过，那么我就狂妄自大一点安上自己的名字吧，先到先得嘛(?) XD） 算了算了 好像有人提过了？ 不管了 有问题欢迎指出！好了，可以开喷了。