谈一类特殊回滚莫队——链表莫队

灵感源自这篇题解，看了很久才看懂，纪念一下。

取这个名字是因为它既不像只增不删也不像只删不增，但其可以维护一类较为有普遍性的问题——区间相邻值最值问题。

例如区间查询值域上连续三个数的差的平方和的最小值，或者求任何关于值域上常数个连续值最值问题（需要保证区间不优于其子集区间，例如 $\min\limits_{i,j}|a_{i}-a_j|,\min\limits_{i,j,k,a_i\ge a_j\ge a_k\ge0}\left(a_i^2-a_j^2+a_j^3-a_k^3\right)$ 等）。

朴素的莫队套std::set或者平衡树是 $O(n\sqrt n\log n)$ 的，死的很惨。

而链表莫队可以在 $O(n\sqrt n)$ 内解决，且常数极小。

有些时候我们朴素莫队移动端点发现需要相邻值的时候通常会想到只删不增套链表，但区间内最值问题并不能通过删除来更新，这就是链表莫队存在的意义。

其主要思想是我们删一个数很好找前驱后继，而加一个数不好找，那我们就先删了再撤销达到加数的效果。

但是如果你尝试写一下这个东西就会发现它的阴间了，各种删除和撤销杂糅在一起，非常难搞。

这里提供一种普遍的写法（用 $L,R$ 代表块端点， $l,r$ 代表询问端点，文字左右端点代表现在的链表区间）：

首先询问挂到 $l$ 所在块，每块按 $r$ 从小到大排序。
处理每块时首先构建 $[L,n]$ 的链表，然后从右往左全删掉。
开始处理询问，每次首先把右端点向右撤销回 $r_i$ （不更新答案），然后将左端点向右删到 $\min(r_i,R)$ （为了统一处理右端点是否在同一块的询问），向左撤回左端点到 $l_i$ （更新答案），然后向左撤回左端点到 $L$ （为了处理下一个询问，不更新答案）。

还没有结束，但我们简单说一下这段干了些什么。

分两类讨论： $r_i\in [L,R]$ 和 $r_i>R$ 。

对于 $r_i\in [L,R]$ 的情况，在向右删左端点的时候直接删到右端点处了，然后向左边撤销边更新答案，直接完成答案的更新。

对于 $r_i>R$ 的情况，我们只删到了 $R$ ，这种情况下链表中还有 $(R,r_i]$ 的元素，我们在向左撤回左端点的时候，处理了 $[l_i,R]$ 与 $(R,r_i]$ 以及 $[l_i,R]$ 对本身的贡献。

那我们欠缺的就是第二种情况下 $(R,r_i]$ 对本身的贡献。

所以接着我们的流程：

此时左端点在 $L$ ，我们将右端点直接撤销回 $n$ ，然后构造从 $R$ 向两边扩展的模型。
具体来说，先将左端点向右删到 $R+1$ ，再将右端点向左删到 $R$ ，此时是空区间。
然后处理 $r_i>R$ 的询问，每次将右端点向右撤销到 $r_i$ （累计更新答案到 $res$ 里面），用 $res$ （也就是从 $R$ 到 $r_i$ 一直扩展以来的最优答案）更新询问答案。

给一下代码：

struct Crl {int x,pr,nx;} crl[N<<1];vector<int> v[N];
void del(int x) {
    x=a[x];bn[x]--;crl[++cnt]={x,pre[x],nxt[x]};
    if(!bn[x]) pre[x]&&(nxt[pre[x]]=nxt[x]),nxt[x]&&(pre[nxt[x]]=pre[x]);
}
int CtrlZ(int len) {
    int res=inf;F(i,1,len) {
        int x=crl[cnt].x,pr=crl[cnt].pr,nx=crl[cnt--].nx;
        pre[x]=pr;nxt[x]=nx;pr&&(nxt[pr]=x);nx&&(pre[nx]=x);bn[x]++;if(bn[x]>=2) res=0;
        pr&&(res=min(res,V[x]-V[pr]));nx&&(res=min(res,V[nx]-V[x]));//此处更新答案依照具体题目而定，本代码是求区间最小差。
    } return res;
}
main:
F(i,1,m=read()) l[i]=read(),r[i]=read(),v[id(l[i])].pb(i),ans[i]=inf;
    F(b,1,id(n)) {
        F(i,1,vnt) pre[i]=nxt[i]=bn[i]=0;cnt=0;//记得把撤销的栈顶清空，否则RE。
        F(i,l(b),n) bn[a[i]]++;
        int lst=0;F(i,1,vnt) bn[i]&&(pre[i]=lst,lst=i);
        lst=0;UF(i,vnt,1) bn[i]&&(nxt[i]=lst,lst=i);//构造链表
        sort(v[b].begin(),v[b].end(),[](int x,int y){return r[x]<r[y];});//1.
        int R=n,L=l(b);while(R>l(b)) del(R--);//2.
        for(int i:v[b]) {//3.
            CtrlZ(r[i]-R);R=r[i];
            while(L<=min(r(b),r[i])) del(L++);
            ans[i]=CtrlZ(L-l[i]);L=l[i];
            CtrlZ(L-l(b));L=l(b);
        } CtrlZ(n-R);R=n;//4.
        while(L<=r(b)) del(L++);//5.
        while(R>r(b)) del(R--);//5.
        int res=inf;for(int i:v[b]) if(r[i]>r(b)) {//6.
            res=min(res,CtrlZ(r[i]-R));R=r[i];
        ans[i]=min(ans[i],res);
    }
} F(i,1,m) printf("%d\n",ans[i]);