WBLT 及 ULR#3F 相关 Trick 笔记

y0y68 · 2026-01-24 11:37:07 · 算法·理论

为什么你必须学习 ULR#3F 因为它是区间查询复合函数的新优选

WBLT

定义

LeafyTree 为信息存储在叶子节点上的树，WBLT 为重量平衡的 LeafyTree。

设节点 o 的重量 w_o 为子树 o 的叶子个数。取常数 \alpha，定义一棵二叉的 LeafyTree 为 WBLT 当且仅当对于每一个非叶子节点 o，其有且仅有两个儿子 x,y 满足 \min(w_x,w_y)\ge \alpha w_o，一般取 \alpha=\frac{1}{4} 时即为 3\min(w_x,w_y)\ge \max(w_x,w_y)。

明显地，对于任意正整数个数的节点，都可以以其为叶子构造一颗 WBLT（直接采用线段树的构造方式）。

定义一个节点 o 有以下信息：

son[o][0/1]：左右儿子 ls rs
       w[o]：重量
     val[o]：子树信息并

定义函数 newnode() 为新建一个节点，若有参数则为复制此节点；

定义 delnode(o) 为删除回收节点 o。

WBLT 在维护过程中会不断新增和删除节点，普通 WBLT 需要使用空间回收来保证空间复杂度正确。

int newnode(int o1=0){
    o=top?stk[top--]:m;
    w[o]=o1?w[o1]:1,tg[o]=tg[o1];
    son[o][0]=son[o1][0];
    son[o][1]=son[o1][1];
    return o;
}
void delnode(int o){stk[++top]=o;}

定义 cmpr(x,y) 为比较重量 x,y 是否平衡：

int cmpr(int x,int y){
    if(y*3ll<x)return 1;
    if(x*3ll<y)return 2;
    return 0;
}

定义 pup(o) 为更新 w_u。

void pup(int o){w[o]=w[ls]+w[rs];}

通过合并/分裂维护 WBLT

定义函数 join(x,y)，cut(x)：

int join(int x,int y){
    int o=newnode();
    ls=x,rs=y;pup(o);
    return o; 
}
pii cut(int o){
    int x=ls,y=rs;
    delnode(o);
    return mkp(x,y);
}

类似 FHQTreap，WBLT 采用递归合并，合并的过程为：

若二子树平衡，则直接合并。

否则按照两种形态合并：

以右边大为例，先拆分 y 节点（断绿边），若此时红色树平衡则连接红色边。

否则拆分 a 节点（断蓝边），连接粉色边。

合并两棵树的复杂度为 \mathcal{O}(\log \frac{w_{\max}}{w_{\min}})。

int mer(int x,int y){
    if(!x||!y)return x|y;
    int op=cmpr(w[x],w[y]);
    if(op==1){
        auto [a,b]=cut(x);
        if(!cmpr(w[a],w[b]+w[y]))return mer(a,mer(b,y));
        auto [c,d]=cut(b);
        return mer(mer(a,c),mer(d,y));
    }
    if(op==2){
        auto [a,b]=cut(y);
        if(!cmpr(w[x]+w[a],w[b]))return mer(mer(x,a),b);
        auto [c,d]=cut(a);
        return mer(mer(x,c),mer(d,b));
    }
    return join(x,y);
}

分裂过程类似线段树分裂，复杂度 \mathcal{O}(\log n)。

pii split(int o,int k){//按照重量分裂
    if(!o)return mkp(0,o);
    if(w[o]<=k)return mkp(o,0);
    int x,y;
    if(k<=w[ls]){
        tie(x,y)=split(ls,k);
        y=mer(y,rs);
    }else{
        tie(x,y)=split(rs,k=w[ls]);
        x=mer(ls,x);
    }
    cut(o);
    return mkp(x,y);
}

如果要实现功能函数，如存储标记等，则每次 cut 时必须把标记 pushdown 到子节点。

WBLT 的可持久化

在以上过程中删去 delnode 即可，每次修改必须新建节点。

inline int newnode(int o=0){
    ++m,w[m]=o?w[o]:1,tg[m]=tg[o];
    son[m][0]=ls,son[m][1]=rs;
    return m;
}
inline int Add(int o,int x){
    o=newnode(o);
    tg[o]=func(o,x);//更新 tag
    return o;
}
inline pii cut(int o){
    int x=ls,y=rs;
    if(tg[o])
        x=Add(x,tg[o]),y=Add(y,tg[o]);
    return mkp(x,y);
}

注意可持久化的 split 有比标记下传常数更小的写法：

int splitL(int o,uint k){//重量 split 左边部分
    if(!k)return 0;
    if(w[o]<=k)return o;
    int x;
    if(k<=w[ls])x=splitL(ls,k);
    else x=mer(ls,splitL(rs,k-w[ls]));
    if(tg[o])x=Add(x,tg[o]);//打标记不用下传
    return x;
}

WBLT 维护区间复制

直接根据可持久化维护区间复制即可。

空间优化：引用计数

这个内容是学弟@Cyril想想告诉我的，他说这个空间是线性的，我不会证。原文链接。

仅实现区间复制不需要令所有节点可持久化，记 ref_o 为节点 o 的父亲个数，为根时额外加 1。

若一个节点的 ref 为 1 时，功能函数操作不需要新建节点。

当一个节点被 delnode 时其 ref_o\gets ref_o-1，为 0 时删除本节点并给子节点的 ref 减 1。

带区间复制 WBLT 代码：

namespace WBLT{
#define ls son[o][0]
#define rs son[o][1]
    const int M=2e7+5;
    Ele val[M];//维护信息
    int w[M];//weight
    int ref[M];//引用计数
    int son[M][2],tot=0;
    int stk[M],top=0;
    int newnode(Ele v=(Ele){0,0,0,0}){
        int o=top?stk[top--]:++tot;
        val[o]=v,w[o]=1;
        ref[o]=1,ls=rs=0;
        return o;
    }
    void delnode(int &o){
        if(--ref[o])return;
        delnode(ls),delnode(rs);
        stk[++top]=o,o=0;
    }
    void pup(int o){
        val[o]=val[ls]+val[rs],w[o]=w[ls]+w[rs];
    }
    int cmpr(int x,int y){
        if(x>y*3)return 1;
        if(y>x*3)return 2;
        return 0;
    }
    int join(int x,int y){
        if(!x||!y)return x|y;
        int o=newnode();
        ls=x,rs=y,pup(o);
        return o;
    }
    pii cut(int &o){
        int x=ls,y=rs;
        ++ref[x],++ref[y];
        delnode(o);
        return mkp(x,y);
    }
    int mer(int x,int y){
        if(!x||!y)return x|y;
        int op=cmpr(w[x],w[y]),a,b,c,d;
        if(op==1){
            tie(a,b)=cut(x);
            if(!cmpr(w[a],w[b]+w[y]))return mer(a,mer(b,y));
            tie(c,d)=cut(b);return mer(mer(a,c),mer(d,y));
        }
        if(op==2){
            tie(a,b)=cut(y);
            if(!cmpr(w[x]+w[a],w[y]))return mer(mer(x,a),b);
            tie(c,d)=cut(a);return mer(mer(x,c),mer(d,b));
        }
        return join(x,y);
    }
    void copy(int o){++ref[o];}
    void query(int o,int lt,int rt,int &x){
        if(!o)return;
        int l=val[o].tl,r=val[o].tr;
        if(r<lt||l>rt)return;
        if(l>=lt&&r<=rt){
            x=(1ll*val[o].k*x+val[o].b)%mod;
            return;
        }
        query(ls,lt,rt,x),query(rs,lt,rt,x);
    }
#undef ls
#undef rs
}

区间复制实现倍增建树

建出大小为 2^n 的平衡树：先建立一个节点为根，进行 root=mer(root,root) 操作 n 次即可构造一个节点数 2^n 的平衡树。

如果你想一开始做一个带标号的，那就在复制的时候给右边的一份打上加标记。

维护区间分段函数

下面的题目中每次执行操作都和当前的某个值的大小有关，我们称这个值为关键值。

关键值不变

P11721 [清华集训 2014] 玄学

每次的操作是对于一段关键值修改答案，而不改变关键值本身。

序列是动态构造的，由于关键值始终不变，则对关键值建立线段树。

由于每次查询一段操作时间上的操作，则内层嵌套平衡树，每次修改操作给 \mathcal{O}(\log n) 个线段树节点的平衡树后加入一个操作。

标记下传时需要合并两个标记，则直接把父亲节点的标记接在子节点的树后，使用 WBLT 维护区间合并即可。

struct Ele{
    int tl,tr,k,b;//操作时间，操作系数
    friend Ele operator +(const Ele &lf,const Ele &rf){
        return (Ele){lf.tl,rf.tr,int(1ll*lf.k*rf.k%mod),int((1ll*lf.b*rf.k+rf.b)%mod)};
    }
};
namespace WBLT{//本题不存在区间修改，即不需要新建节点
#define ls son[o][0]
#define rs son[o][1]
    const int M=2e7+5;
    Ele val[M];//维护信息
    int w[M];//weight
    int ref[M];//引用计数
    int son[M][2],tot=0;
    int stk[M],top=0;
    int newnode(Ele v=(Ele){0,0,0,0}){
        int o=top?stk[top--]:++tot;
        val[o]=v,w[o]=1;
        ref[o]=1,ls=rs=0;
        return o;
    }
    void delnode(int &o){
        if(--ref[o])return;
        delnode(ls),delnode(rs);
        stk[++top]=o,o=0;
    }
    void pup(int o){
        val[o]=val[ls]+val[rs],w[o]=w[ls]+w[rs];
    }
    int cmpr(int x,int y){
        if(x>y*3)return 1;
        if(y>x*3)return 2;
        return 0;
    }
    int join(int x,int y){
        if(!x||!y)return x|y;
        assert(!cmpr(w[x],w[y]));
        int o=newnode();
        ls=x,rs=y,pup(o);
        return o;
    }
    pii cut(int &o){
        assert(w[o]>1);
        int x=ls,y=rs;
        ++ref[x],++ref[y];
        delnode(o);
        return mkp(x,y);
    }
    int mer(int x,int y){
        if(!x||!y)return x|y;
        int op=cmpr(w[x],w[y]),a,b,c,d;
        if(op==1){
            tie(a,b)=cut(x);
            if(!cmpr(w[a],w[b]+w[y]))return mer(a,mer(b,y));
            tie(c,d)=cut(b);return mer(mer(a,c),mer(d,y));
        }
        if(op==2){
            tie(a,b)=cut(y);
            if(!cmpr(w[x]+w[a],w[y]))return mer(mer(x,a),b);
            tie(c,d)=cut(a);return mer(mer(x,c),mer(d,b));
        }
        return join(x,y);
    }
    void bal(int &o){
        if(w[o]==1)return;
        if(cmpr(w[ls],w[rs])){
            int a,b;tie(a,b)=cut(o);
            o=mer(a,b);
        }
    }
    void copy(int o){++ref[o];}
    void query(int o,int lt,int rt,int &x){
        if(!o)return;
        int l=val[o].tl,r=val[o].tr;
        if(r<lt||l>rt)return;
        if(l>=lt&&r<=rt){
            x=(1ll*val[o].k*x+val[o].b)%mod;
            return;
        }
        query(ls,lt,rt,x),query(rs,lt,rt,x);
    }
#undef ls
#undef rs
}
int a[N],n,m,q,Ans=0;
namespace sgt{
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
    const int M=4e5+5;
    int root[M];//标记（平衡树）
    void Mer(int o,int rtx){
        WBLT::copy(rtx);
        root[o]=WBLT::mer(root[o],rtx);
    }
    void psd(int o){
        if(root[o]){
            Mer(ls,root[o]),Mer(rs,root[o]);
            WBLT::delnode(root[o]);
            root[o]=0;
        }
    }
    void ins(int o,int l,int r,int lt,int rt,int rtx){
        if(l>=lt&&r<=rt)return Mer(o,rtx);
        psd(o);
        if(lt<=mid)ins(ls,l,mid,lt,rt,rtx);
        if(rt> mid)ins(rs,mid+1,r,lt,rt,rtx);
    }
    int query(int o,int l,int r,int p,int lt,int rt){
        if(l==r){
            int x=a[p];WBLT::query(root[o],lt,rt,x);
            return x;
        }
        psd(o);
        return (p<=mid?query(ls,l,mid,p,lt,rt):query(rs,mid+1,r,p,lt,rt));
    }
#undef ls
#undef rs
#undef mid

关键值改变

P8264 [Ynoi Easy Round 2020] TEST_100

每次的操作是对于一段关键值修改答案并改变关键值本身。

对比上一题，本题关键值存在移动，答案不再保持线性段，考虑倒序维护：

假设我们总是询问操作编号在 [l,n] 的操作并，本题中，我们相当于把一个答案区间复制了两份到另一个区间，并给复制后的区间进行加减/文艺操作，直接使用平衡树倒序扫描即可。

考虑操作编号不再是后缀，此时外层套一个线段树，内层先使用前文所述倍增建树，然后倒序模拟操作即可。

为什么不正序维护？正序维护要求把两个不同答案合并到同一个地方，这是一个对位的操作，不方便维护；而倒序下正好相反，是把一个相同的答案复制一份到别的地方，可以用平衡树快速维护。

代码懒了。

全局平衡二叉树

这个东西结构上基本等于静态 TopTree（重链上平衡 compress，轻边 rake）。

树链剖分后对于每条重链进行重量平衡：即每个节点重新记录 sz 二分中点建树。

较为简单的说，就是根据重量重新平衡了每条重链的线段树（普通二叉树形式）。

明显地，两部分平衡之后，每一部分都只会跳 \mathcal{O}(\log n) 次。

建树代码：

vector<int>e[N];
int fa[N],d[N],sz[N],hs[N],n;
void dfs(int u,int Fa,int D){//重剖
    fa[u]=Fa,d[u]=D;
    for(auto v:e[u])if(v!=Fa){
        dfs(v,u,D+1),sz[u]+=sz[v];
        if(sz[v]>=sz[hs[u]])hs[u]=v;
    }
}
int ch[N][2];//二叉树重边
int up[N];//二叉树父亲
int dfn[N];//链上编号
int L[N],R[N];//二叉树子树的最小/最大 dfn
int sum[N],stk[N],top=0;
【节点信息】val[N];
int buildc(int l,int r,int Fa){
    int md=(l==r)?l:lower_bound(sum+l,sum+r+1,(sum[l]+sum[r])>>1)-sum;
    int u=stk[md];
    up[u]=Fa,L[u]=R[u]=dfn[u];
    if(l<md){
        ch[u][0]=buildc(l,md-1,u),L[u]=L[ch[u][0]];
        【合并左边节点信息】
    }
    【处理当前节点信息】
    if(r>md){
        ch[u][1]=buildc(md+1,r,u),R[u]=R[ch[u][1]];
        【合并右边节点信息】
    }
    return u;
}
void build(){
    dfs(1,0,0);
    for(int st=1;st<=n;st++)if(st!=hs[fa[st]]){
        top=0;
        for(int x=st;x;x=hs[x])stk[++top]=x,dfn[x]=top;
        buildc(1,top,0);
    }
}

DAG 链剖分

对于本题的 DAG，每个点选取子节点中路径条数（sz）最多的节点作为后继，每个非零度节点选择最多的作为前驱。

写成代码即：

for(int i=1+n;i<=m;i++){
    bool op=(sz[son[i][0]]<sz[son[i][1]]);
    if(sz[i]>sz[pre[son[i][op]]])pre[son[i][op]]=i;
}
for(int i=1;i<=m;i++)if(pre[i])hs[pre[i]]=i;

类似全局平衡二叉树形态的 DAG 剖分

对于符合条件的 DAG 同样对于每条链建立类似结构：

     up[u]：二叉树结构父亲
    dfn[u]：u 在链上的顺序
ch[u][0/1]：u 在二叉树结构上的左右儿子
 L[u],R[u]：（二叉树）子树所占链上区间

int buildc(int l,int r,int Fa){
    int md=((l==r)?l:lower_bound(sum+l,sum+r+1,(sum[l-1]+sum[r])>>1)-sum);
    int u=stk[md];
    up[u]=Fa,L[u]=l,R[u]=r,sm[u]=(Node){0,1,0};
    if(l<md)ch[u][0]=buildc(l,md-1,u),sm[u]=sm[u]+sm[ch[u][0]];
    if(hs[u]==son[u][1])sm[u]=sm[u]+nd[son[u][0]];
    if(md<r)ch[u][1]=buildc(md+1,r,u),sm[u]=sm[u]+sm[ch[u][1]];
    return u;
}
void build(int n){
    for(int i=1+n;i<=m;i++){
        bool op=(sz[son[i][0]]<sz[son[i][1]]);
        if(sz[i]>sz[pre[son[i][op]]])pre[son[i][op]]=i;
    }
    for(int i=1;i<=m;i++)if(pre[i])hs[pre[i]]=i;
    for(int st=m;st;st--)if(!pre[st]){
        top=0;
        for(int x=st;x;x=hs[x])
            stk[++top]=x,dfn[x]=top;
        sum[top]=sz[st];
        for(int i=1;i<top;i++)sum[i]=sz[st]-sz[stk[i+1]];
        buildc(1,top,0);
    }
}

在剖分结构上向下跳链查询

直接套用全局平衡二叉树的做法，在每条重链上跳并寻找跳轻边的点。

注意这道题我们要求的是一条右边的链以及其左边的答案。

本题重链向下的 tl 不降，tr 不增。

代码见后文。

解决方法

官方题解。

这道题目的关键值 X 随操作变化，而且要做区间查询，没有修改操作，考虑结合前文两题的做法。

外层维护可持久化 WBLT，倒序扫描时，每次操作相当于分裂一段再合并。

内层维护支持复制树形数据结构，先继续采用 WBLT，每次分裂时把 tag 下传至儿子并与之合并。

考虑一次查询操作：从外层树的某个节点开始向下查找：

每次遇到 tag 就在内层树上查找。

当然我们所有的查询都是一个前缀（取出的根是 root_l，这时还未有 <l 的节点出现），所以需要在内层树上查询的节点只有至多 1 个。

当前预处理 \mathcal{O}(n\log V \log n)，查询复杂度 \mathcal{O}(n\log V)（我的树套树只有 55pts）。

考虑所有内层树的结构其实是一个 DAG，所以对于内层树，直接使用不平衡的 LeafyTree 代替，现在合并变成了 \mathcal{O}(1)。建立剖分结构之后，考虑用 DAG 上查询代替平衡树查询。

内层树的节点个数为 \mathcal{O}(n\log V)，路径条数为 \mathcal{O}(n^2\log V)。

下面实现的 DAG 链剖分大量cpy参考了wzc_IOI_czw 的代码。

套用上文的 DAG 链剖分，由于链剖分的复杂度是节点数线性的，则预处理复杂度降低到了 \mathcal{O}(n\log V)。

前面的实现是简易的，考虑 DAG 链剖分的实现：

内层 DAG 每个点有数据 tl,tr 代表子树操作的最小时间和最大时间，nd 代表子树操作信息并。

我们从某个点开始向下查询“子树”中操作时间在 [l,r] 之间的所有叶子节点的操作信息并。

每次查询时，要定位靠右边的链并获取链左侧所有子树的信息并，这个是容易在轻子树信息中维护的。

对于一条重链，向下时每个点的 tl 不降，tr 不增，则可以直接在当前链的二叉树上二分找到最后一个当前链节点。

接着查询当前链节点并跳轻边到子节点上，不断循环本操作即可。

内层树+外层跳链的复杂度依然满足类似全局平衡二叉树的性质，则查询复杂度为 \mathcal{O}(\log S),S=\mathcal{O}(n^2\log V)。

疑问：我的 DAG 链剖分部分代码基本是由上文链接中提交改来的，官解中“由于全局平衡的 DAG 剖分需要使用 finger search” 一句并没有理解，所以我代码的复杂度也许有误。

具体实现（目前是最优解）：

#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
template<typename T>void in(T &n){n=0;char c=getchar();bool flag=0;for(;c<'0'||c>'9';c=getchar())if(c=='-')flag=1;for(;c>='0'&&c<='9';c=getchar())(n*=10)+=(c^48);if(flag)n=-n;}
int wlsk[45];int wltp;
template<typename T>void out(T n,char c=0){if(n==0){putchar('0');if(c)putchar(c);return;}if(n<0)putchar('-'),n=-n;while(n) wlsk[++wltp]=(n%10),n/=10;while(wltp) putchar(wlsk[wltp--]^48);if(c)putchar(c);}
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
const int N=2e5+5,M=1e7+5,M2=3e7+5;
const uint inf=2147483647;
struct Node{
    uint y,a,b;
    inline friend Node operator +(const Node &lf,const Node &rf){return (Node){lf.y+rf.y,lf.a*rf.a,rf.b+rf.a*lf.b};}
}nd[M];
int n;
namespace DAG{
    Node sm[M];
    int son[M][2],tl[M],tr[M],sz[M],m;
    int pre[M],hs[M];
    int dfn[M],up[M],ch[M][2],L[M],R[M];
    int stk[M],sum[M],top;
    //up 的含义更改为向上最近的覆盖链后缀的节点，减小常数（这里你改为父亲/二叉树根都行）
    inline int mer(int x,int y){
        if(!x||!y)return x|y;
        m++;
        son[m][0]=x,son[m][1]=y;
        tl[m]=tl[x],tr[m]=tr[y];
        nd[m]=nd[x]+nd[y],sz[m]=sz[x]+sz[y];
        return m;
    }
    int buildc(int l,int r,int Fa){
        int md=((l==r)?l:lower_bound(sum+l,sum+r+1,(sum[l-1]+sum[r])>>1)-sum);
        int u=stk[md];if(r==top)Fa=u;
        up[u]=Fa,L[u]=l,R[u]=r,sm[u]=(Node){0,1,0};
        if(l<md)
            ch[u][0]=buildc(l,md-1,Fa),sm[u]=sm[u]+sm[ch[u][0]];
        if(hs[u]==son[u][1])
            sm[u]=sm[u]+nd[son[u][0]];//轻子树信息
        if(md<r)
            ch[u][1]=buildc(md+1,r,Fa),sm[u]=sm[u]+sm[ch[u][1]];
        return u;
    }
    void build(int n){
        for(int i=1+n;i<=m;i++){
            bool op=(sz[son[i][0]]<sz[son[i][1]]);
            if(sz[i]>sz[pre[son[i][op]]])pre[son[i][op]]=i;
        }
        for(int i=1;i<=m;i++)if(pre[i])hs[pre[i]]=i;
        for(int st=m;st;st--)if(!pre[st]){
            top=0;
            for(int x=st;x;x=hs[x])
                stk[++top]=x,dfn[x]=top;
            sum[top]=sz[st];
            for(int i=1;i<top;i++)sum[i]=sz[st]-sz[stk[i+1]];
            buildc(1,top,0);
        }
    }
    Node query(int u,int lt,int rt){
        if(!u)return (Node){0,1,0};
        if(lt<=L[u]&&R[u]<=rt)return sm[u];
        Node res=(Node){0,1,0};
        if(lt<dfn[u])res=res+query(ch[u][0],lt,rt);
        if(lt<=dfn[u]&&rt>=dfn[u]&&(hs[u]==son[u][1]))res=res+nd[son[u][0]];
        if(rt>dfn[u])res=res+query(ch[u][1],lt,rt);
        return res;
    }//二叉树上查询
    Node qry(int u,int R){//定位右侧链查左侧答案
        if(R<tl[u])return (Node){0,1,0};
        if(tr[u]<=R)return nd[u];
        Node res=(Node){0,1,0};
        while(tl[u]<=R){
            int v=up[u],ed=u;
            while(v){//tl up,tr down
                //定位重链上最后一点
                if(tl[v]<=R&&tr[v]>R)ed=v,v=ch[v][1];
                else v=ch[v][0];
            }
            if(dfn[u]<dfn[ed])res=res+query(up[u],dfn[u],dfn[ed]-1);
            if(ed<=n)break;//到叶子了

            if(tr[son[ed][0]]<=R)res=res+nd[son[ed][0]],u=son[ed][1];
            else u=son[ed][0];//跳链
        }
        return res;
    }
}
#define ls son[o][0]
#define rs son[o][1]
namespace WBLT{
    int son[M2][2],tg[M2],m,tm;
    uint w[M2];
    inline void reft(){tm=m;}
    inline int cmpr(int x,int y){
        if(y*3ll<x)return 1;
        if(x*3ll<y)return 2;
        return 0;
    }
    inline int newnode(int o=0){
        if(o>tm)return o;
        ++m,w[m]=o?w[o]:1,tg[m]=tg[o];
        son[m][0]=ls,son[m][1]=rs;
        return m;
    }
    inline void pup(int o){w[o]=w[ls]+w[rs];}
    inline int Add(int o,int x){o=newnode(o);tg[o]=DAG::mer(x,tg[o]);return o;}
    inline int join(int x,int y){
        int o=newnode();
        ls=x,rs=y;pup(o);
        return o; 
    }
    inline pii cut(int o){
        int x=ls,y=rs;
        if(tg[o])
            x=Add(x,tg[o]),y=Add(y,tg[o]);
        return mkp(x,y);
    }
    int mer(int x,int y){
        if(!x||!y)return x|y;
        int op=cmpr(w[x],w[y]);
        if(op==1){
            auto [a,b]=cut(x);
            if(!cmpr(w[a],w[b]+w[y]))return mer(a,mer(b,y));
            auto [c,d]=cut(b);
            return mer(mer(a,c),mer(d,y));
        }
        if(op==2){
            auto [a,b]=cut(y);
            if(!cmpr(w[x]+w[a],w[b]))return mer(mer(x,a),b);
            auto [c,d]=cut(a);
            return mer(mer(x,c),mer(d,b));
        }
        return join(x,y);
    }
    int splitL(int o,uint k){
        if(!k)return 0;
        if(w[o]<=k)return o;
        int x;
        if(k<=w[ls])x=splitL(ls,k);
        else x=mer(ls,splitL(rs,k-w[ls]));
        if(tg[o])x=Add(x,tg[o]);
        return x;
    }
    int splitR(int o,uint k){
        if(!k)return o;
        if(w[o]<=k)return 0;
        int x;
        if(k<=w[ls])x=mer(splitR(ls,k),rs);
        else x=splitR(rs,k-w[ls]);
        if(tg[o])x=Add(x,tg[o]);
        return x;
    }
    Node qry(int o,int X,int rt){
        Node res=(Node){0,1,0};
        while(o){
            if(tg[o])res=res+DAG::qry(tg[o],rt);
            if(w[o]==1)break;
            X<=w[ls]?o=ls:(X-=w[ls],o=rs);
        }
        return res;
    }
}
#undef ls
#undef rs
int root[N],LT[N],q;
int xo[N],yo[N];
uint ao[N],bo[N];
uint LST;
int main(){
    in(n),in(q);
    for(int i=1;i<=n;i++)
        in(xo[i]),in(yo[i]),in(ao[i]),in(bo[i]);
    for(int i=1;i<=n;i++)
        LT[n+1]=min(0,int(LT[n+1]+yo[i]));
    root[n+1]=WBLT::newnode(),WBLT::reft();
    for(int b=1;b<inf;b<<=1)
        root[n+1]=WBLT::mer(root[n+1],root[n+1]),WBLT::reft();
    DAG::m=n,nd[0]=(Node){0,1,0};
    for(int i=1;i<=n;i++){
        DAG::tl[i]=DAG::tr[i]=i;
        DAG::sz[i]=1;
        nd[i]=(Node){yo[i],ao[i],bo[i]};
    }
    for(int x,y,i=n;i;i--){
        y=WBLT::splitR(root[i+1],xo[i]-LT[i+1]+1);
        x=WBLT::splitL(root[i+1],xo[i]+yo[i]-LT[i+1]+1);
        root[i]=WBLT::mer(WBLT::Add(x,i),y);
        WBLT::reft(),LT[i]=LT[i+1]-yo[i];
    }
    DAG::build(n);
    uint X,lt,rt;
    long long TX,TL,TR;
    while(q--){
        in(TL),in(TR),in(TX);
        X=TX,lt=TL,rt=TR,X^=LST,lt^=LST,rt^=LST;
        Node Ans=WBLT::qry(root[lt],X-LT[lt]+1,rt);
        out(int(X+Ans.y),' '),out(Ans.a,' '),out(Ans.b,'\n');
        LST=Ans.a^Ans.b;
    }
    return 0;
}

解决一个有趣的题目是一个有趣的过程，能学到很多有趣的东西。