最近做题的时候想到了一种将莫队强制在线的方法，就是下面这道题：
给定长为 \(n\) 的序列 \(A\) ，其中所有元素满足 \(x \in [1,n]\)，\(m\) 次询问某个区间 \([l,r]\) 内的第 \(k\) 小值，若某个数的出现次数大于 \(w\) ，则这个数在此询问中被视为 \(n+1\)， \(w\) 是一给定常数，强制在线 \(n,m\leq 10^5\)
正解分块即可，但凭着一颗爱捣腾的心，当然要用莫队来做，这种题若是离线用莫队解非常方便，但由于这题强制在线，不能直接上莫队
考虑下莫队的原理：可以快速地由区间 \([l,r]\) 的答案转移到区间 \([l\pm 1,r\pm 1]\) 的答案，复杂度分析大概是将一个对区间 \([l,r]\) 的询问化为一个 \((l,r)\) 的在二维平面上的点，由一个点 \((l_1,r_1)\) 到 \((l_2,r_2)\) 的转移代价为 \(|l_1-l_2|+|r_1-r_2|\) 也即曼哈顿距离，整个算法相当于是一个点在平面上连出一条贯穿所有节点的链出来，复杂度即为这条链的总长（曼哈顿距离）。在对左端点分块、块内按右端点排序的情况下，设块大小为 \(S\)，则复杂度为 \(O(mS+\frac {n^2}S)\)，在 \(n,m\) 同阶的情况下取 \(S=\sqrt n\) 复杂度最优，为 \(O((n+m)\sqrt n)\)
但上面这种方法仅限于提前得知了所有的询问（即平面上点的位置），若是强制在线，这个做法可以被卡到 \(O(nm)\)，于是就有了下面这个想法：在离线莫队的做法里，是让一个节点（初始状态）按照构造出的一条长度为 \(O(n\sqrt n)\) 的曼哈顿路线行走，但若要强制在线，则只能按照题目询问的顺序走，运行时间完全由输入掌握。一种简单的想法是：构造多条路线
考虑在平面上保存多个节点，当前询问则由最近的节点进行移动求解，在保存足够多的点时，可以保证复杂度不受输入影响（相当于保存多个莫队进程）
则这样的复杂度为 “放置这些点的复杂度” + “离平面上最近的点曼哈顿距离的最大值”，复杂度完全依赖于放点的方案
我目前使用的是将点放成一个矩形，设矩形大小为 \(S\times S\)，则构造这些点的复杂度为 \(O(nS^2)\)，而平面上被分为了 \(\frac nS\times \frac nS\) 的块，则平面上离点最近距离的最大值约为 \(\frac n{2S}\)，则询问复杂度为 \(O(\frac n{2S}\cdot m)\)，总复杂度 \(O(nS^2+\frac {nm}{2S})\)，若 \(n,m\) 同阶的情况下，取 \(S=m^{\frac 13}\) 最优，时间与空间复杂度皆为 \(O(m^{\frac 23}n)\)
实际运行效率？在上面的这题中 \((n,m\leq 10^5)\)，开 \(\mathrm {O2}\) 优化，运行时间约为 \(1.8s\) （正解分块约为 \(1.1s\)），码量比正解小了不少
贴上代码：
#include <bits/stdc++.h> using namespace std; inline void read(int&x){ char c11=getchar();x=0;while(!isdigit(c11))c11=getchar(); while(isdigit(c11))x=x*10+c11-'0',c11=getchar(); } const int N = 100103; int a[N],id[N],L[N],R[N]; int bs[53][53],tot; int n,Q,w; struct Cap_Mo{ int tng[N],cnt[331],bl,br; inline void add(int x){ if(tng[x] == w) {cnt[id[x]] -= tng[x], ++tng[x]; return ;} ++tng[x]; if(tng[x] <= w) ++cnt[id[x]]; } inline void del(int x){ if(tng[x] == w+1) {--tng[x], cnt[id[x]] += tng[x]; return ;} --tng[x]; if(tng[x] <= w) --cnt[id[x]]; } void prework(int l,int r){ bl = l, br = r; for(int i=l;i<=r;++i) add(a[i]); } int query(int k){ int i,j; for(i=1;L[i];++i){ if(k <= cnt[i]) break; k -= cnt[i]; } for(j=L[i];j<=R[i];++j) if(tng[j] <= w){ if(k <= tng[j]) return j; k -= tng[j]; } return n+1; } int work(int ql,int qr,int k){ int l = bl, r = br; while(ql < l) --l, add(a[l]); while(r < qr) ++r, add(a[r]); while(l < ql) del(a[l]), ++l; while(qr < r) del(a[r]), --r; int res = query(k); while(bl < l) --l, add(a[l]); while(r < br) ++r, add(a[r]); while(l < bl) del(a[l]), ++l; while(br < r) del(a[r]), --r; return res; } }base[2213]; int main(){ freopen("in","r",stdin); read(n), read(Q), read(w); for(int i=1;i<=n;++i) read(a[i]); int blk = sqrt(n*1.0), S = min(blk,47); for(int t=1,i=1;i<=n+1;i+=blk,++t){ L[t] = i, R[t] = min(i+blk-1,n+1); for(int j=L[t];j<=R[t];++j) id[j] = t; } for(int i=1;i<=S;++i) for(int j=i;j<=S;++j) base[bs[i][j] = ++tot].prework(i*n/S,j*n/S); int Base_Blk = n / S; int l,r,k,las = 19260817; while(Q--){ read(l), read(r), read(k); l ^= las, r ^= las, k ^= las; int ix = min(max(l/Base_Blk,1),S), iy = min(max(r/Base_Blk,1),S); int dl = abs(base[bs[ix][iy]].bl-l), dr = abs(base[bs[ix][iy]].br-r); if(ix != 1 and abs(base[bs[ix-1][iy]].bl-l) < dl) --ix; if(ix != iy and abs(base[bs[ix+1][iy]].bl-l) < dl) ++ix; if(iy != ix and abs(base[bs[ix][iy-1]].br-r) < dr) --iy; if(iy != n and abs(base[bs[ix][iy+1]].br-r) < dr) ++iy; printf("%d\n",las=base[bs[ix][iy]].work(l,r,k)); } return 0; }