最近做题的时候想到了一种将莫队强制在线的方法，就是下面这道题：
给定长为 (n) 的序列 (A) ，其中所有元素满足 (x in [1,n])，(m) 次询问某个区间 ([l,r]) 内的第 (k) 小值，若某个数的出现次数大于 (w) ，则这个数在此询问中被视为 (n+1)， (w) 是一给定常数，强制在线 (n,mleq 10^5)
正解分块即可，但凭着一颗爱捣腾的心，当然要用莫队来做，这种题若是离线用莫队解非常方便，但由于这题强制在线，不能直接上莫队
考虑下莫队的原理：可以快速地由区间 ([l,r]) 的答案转移到区间 ([lpm 1,rpm 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(nsqrt n)) 的曼哈顿路线行走，但若要强制在线，则只能按照题目询问的顺序走，运行时间完全由输入掌握。一种简单的想法是：构造多条路线
考虑在平面上保存多个节点，当前询问则由最近的节点进行移动求解，在保存足够多的点时，可以保证复杂度不受输入影响（相当于保存多个莫队进程）
则这样的复杂度为 “放置这些点的复杂度” + “离平面上最近的点曼哈顿距离的最大值”，复杂度完全依赖于放点的方案
我目前使用的是将点放成一个矩形，设矩形大小为 (S imes S)，则构造这些点的复杂度为 (O(nS^2))，而平面上被分为了 (frac nS imes 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,mleq 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
",las=base[bs[ix][iy]].work(l,r,k));
}
return 0;
}