题解：P16451 rvtmpq

· · 题解

题意简述

给定一棵带点权 a_i,b_i 的树。每次把编号区间 [l,r] 中所有点的最小连通块内的 a_i 增加 vb_i，并查询单点 a_x 或根到 x 的路径权值和。所有运算均对 2^{32} 取模，输入强制在线。

解题思路

把树根定为 1。记一次修改对应的连通块为 f([l,r])，区间内所有点的 LCA 为 g。

先考虑如何判断连通块与根链的交集。设 y 是 x 的最深祖先，且 y 的子树内存在编号属于 [l,r] 的点。若 g 不是 x 的祖先，根到 x 的路径与连通块不相交；否则交集恰好是路径 g\sim y。特别地，x\in f([l,r]) 当且仅当 g 是 x 的祖先且 y=x。

把区间内各点的 DFS 序看作一个值域区间查询。所求 y 只可能是 x 与两类点的 LCA 中较深者：DFS 序不大于 \operatorname{dfn}(x) 的最大点，以及不小于 \operatorname{dfn}(x) 的最小点。

按编号排列 DFS 序，记 d_i=\operatorname{dfn}(i)。 对序列 d 建立小波矩阵。 先统计区间内小于给定值的元素个数。 再求对应的第 k 小值， 即可分别得到前驱和后继。 最后用 DFS 序 RMQ 求两次 LCA， 便能在 O(\log n) 时间内得到 y。

对操作序列分块，块长取 T=900。已经重构的修改直接计入 a，并维护根链上的 a、b 前缀和。块内尚未重构的修改逐个处理。单点查询用上面的判定决定是否增加 vb_x；路径查询在 g 是 x 祖先时增加 v(S_y-S_{\operatorname{fa}(g)})，其中 S 是 b 的根链前缀和。

重构时，需要一次求出每个点被块内修改覆盖的总系数。对任意点 x，先判断子树与 [l,r] 是否有交点。再减去 x 是 g 严格祖先的情况。后一部分是根到 \operatorname{fa}(g) 的链加，可以用树上差分统一处理。

设 C_x 为 x 子树内所有点的编号集合。把补集的极大连续段称为缺口。区间 [l,r] 与 C_x 不相交，当且仅当它完整落在某个缺口内。记 F(L,R) 为块内修改权值和。其统计条件为 L\le l\le r\le R。块内端点离散化后建立二维后缀、前缀和。预处理耗时 O(T^2)，每次求 F(L,R) 只需 O(1)。

还需得到每个 C_x 的所有缺口贡献。对子树编号集合小并大。把编号 p 插入有序集合，设其前驱、后继为 u,v。缺口贡献 D 的变化为：

D\to D-F(u+1,v-1)+F(u+1,p-1)+F(p+1,v-1)

所有插入三元组只与树有关，可以在读入后预处理。每个编号经过轻边时才会再次插入，因此三元组总数为 O(n\log n)。每次重构按重儿子到父亲的顺序重放这些变化，即可求出所有子树与区间相交的修改权值和。再合并树上差分，便得到每个点的总修改系数。

预处理时间复杂度为 O(n\log^2 n)。每块重构的时间复杂度为 O(n\log n+T^2)，块内查询总计为 O(T^2\log n)。总时间复杂度为 O(n\log^2 n+\frac{qn\log n}{T}+qT\log n)，空间复杂度为 O(n\log n+T^2)。

正确性证明

先证明根链交集的刻画。f([l,r]) 是从 g 到区间内每个点的路径之并。若 g 不是 x 的祖先，这些路径都位于 g 的子树内。它们不会经过根到 x 的路径。若 g 是 x 的祖先，根链上的点属于该并集，当且仅当其子树内含有区间点。因此交集从 g 开始，终止于满足该条件的最深祖先 y。这也说明 x 属于连通块当且仅当 y=x。

再证明前驱、后继足以求出 y。对 x 的任意祖先 z，其子树对应一段 DFS 序区间。该区间包含 \operatorname{dfn}(x)。若某个区间点落在该段内，则某个最近的相邻点也落在其中。这个点是 \operatorname{dfn}(x) 左侧的前驱或右侧的后继。反之亦然。因此，分别与这两个相邻点求 LCA。其中较深者恰好是所求的最深祖先。

接着证明重构公式。若 x 的子树与 [l,r] 没有交点，则 x 不在连通块内。若二者有交点，x 是某个区间点的祖先。此时 x 不在连通块内的唯一情况，是它严格位于 g 上方。故「子树相交」减去「g 的严格祖先」，恰好等于连通块的点集指示量。

对固定的 C_x，若修改区间与其不相交，整个区间会落在补集的某个极大连续段中。这个缺口唯一。反之亦然。不同缺口不会重复统计同一次修改。因此，块内总权值减去所有缺口的 F 值，正好是子树与修改区间相交的权值和。

小并大从重儿子的集合开始，依次插入其余编号。每次插入只会把原缺口 [u+1,v-1] 替换成 [u+1,p-1] 与 [p+1,v-1]，所以转移式始终精确维护当前集合的缺口贡献。全部插入后，集合正是 C_x。归纳可得，每个点的子树相交权值和均被正确求出。

重构把上述系数乘以 b_i 加入 a_i；块内查询则逐次加入尚未重构的同一贡献。两部分互不重叠，合并后包含全部历史修改。故每次单点查询和路径查询都输出正确答案。

参考代码

#include <bits/stdc++.h>
using namespace std;

using uint=uint32_t;
const int N=800005;
const int M=1<<20;
const int E=1600005;
const int K=20;
const int B=900;
const int C=(B+2)*(B+2);
const int inf=0x3f3f3f3f;
struct Insert
{
    int pre,pos,nxt;
};
struct Update
{
    int l,r,g;
    uint v;
};
int head[N],to[E],nxt[E],ec;
int fa[N],dep[N],tin[N],tout[N],rev[N],ord[N];
int siz[N],son[N],stk[N],it[N],lg[N];
int st[K][N],zc[K][N],mid[K];
int mn[M<<1],mx[M<<1];
int li[N],ri[N];
int wx[N],wy[N],cx[B+5],cy[B+5];
uint a[N],b[N],s[N],sb[N],bad[N],neg[N];
uint mat[C];
size_t beg[N],cnt[N];
set<int> *ps[N];
vector<Insert> ins;
Update up[B+5];
int uc;
int n;
void add_edge(int u,int v)
{
    to[++ec]=v;
    nxt[ec]=head[u];
    head[u]=ec;
}
void build_tree()
{
    int top=1,tim=1;
    stk[1]=1;
    it[1]=head[1];
    tin[1]=1;
    rev[1]=ord[1]=1;
    while(top)
    {
        int u=stk[top];
        if(it[top])
        {
            int i=it[top];
            it[top]=nxt[i];
            int v=to[i];
            if(v==fa[u])continue;
            fa[v]=u;
            dep[v]=dep[u]+1;
            tin[v]=++tim;
            rev[tim]=ord[tim]=v;
            stk[++top]=v;
            it[top]=head[v];
        }
        else
        {
            tout[u]=tim;
            top--;
        }
    }
    for(int i=n;i;i--)
    {
        int u=ord[i];
        siz[u]++;
        if(fa[u])
        {
            siz[fa[u]]+=siz[u];
            if(siz[u]>siz[son[fa[u]]])son[fa[u]]=u;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int u=ord[i];
        s[u]=s[fa[u]]+a[u];
        sb[u]=sb[fa[u]]+b[u];
    }
}
void build_lca()
{
    lg[1]=0;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++)st[0][i]=rev[i];
    for(int j=1;j<K;j++)
    {
        int len=1<<(j-1);
        for(int i=1;i+(len<<1)-1<=n;i++)
        {
            int u=st[j-1][i],v=st[j-1][i+len];
            st[j][i]=dep[u]<dep[v]?u:v;
        }
    }
}
int lca(int u,int v)
{
    int x=tin[u],y=tin[v];
    if(x>y)swap(x,y);
    if(x==y)return u;
    x++;
    int k=lg[y-x+1];
    int p=st[k][x],q=st[k][y-(1<<k)+1];
    return fa[dep[p]<dep[q]?p:q];
}
void build_range()
{
    fill(mn,mn+(M<<1),inf);
    for(int i=1;i<=n;i++)mn[M+i-1]=mx[M+i-1]=tin[i];
    for(int i=M-1;i;i--)
    {
        mn[i]=min(mn[i<<1],mn[i<<1|1]);
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
    }
}
int range_lca(int l,int r)
{
    l+=M-1;
    r+=M-1;
    int x=inf,y=0;
    while(l<=r)
    {
        if(l&1){x=min(x,mn[l]);y=max(y,mx[l]);l++;}
        if(!(r&1)){x=min(x,mn[r]);y=max(y,mx[r]);r--;}
        l>>=1;
        r>>=1;
    }
    return lca(rev[x],rev[y]);
}
void build_wavelet()
{
    for(int i=0;i<n;i++)wx[i]=tin[i+1];
    for(int k=K-1;k>=0;k--)
    {
        zc[k][0]=0;
        for(int i=0;i<n;i++)zc[k][i+1]=zc[k][i]+!((wx[i]>>k)&1);
        mid[k]=zc[k][n];
        int l=0,r=mid[k];
        for(int i=0;i<n;i++)
        {
            if((wx[i]>>k)&1)wy[r++]=wx[i];
            else wy[l++]=wx[i];
        }
        swap(wx,wy);
    }
}
int count_less(int l,int r,int x)
{
    l--;
    int res=0;
    for(int k=K-1;k>=0;k--)
    {
        int zl=zc[k][l],zr=zc[k][r];
        if((x>>k)&1)
        {
            res+=zr-zl;
            l=mid[k]+l-zl;
            r=mid[k]+r-zr;
        }
        else
        {
            l=zl;
            r=zr;
        }
    }
    return res;
}
int kth(int l,int r,int p)
{
    l--;
    int res=0;
    for(int k=K-1;k>=0;k--)
    {
        int zl=zc[k][l],zr=zc[k][r];
        int z=zr-zl;
        if(p<=z)
        {
            l=zl;
            r=zr;
        }
        else
        {
            p-=z;
            l=mid[k]+l-zl;
            r=mid[k]+r-zr;
            res|=1<<k;
        }
    }
    return res;
}
int prev_value(int l,int r,int x)
{
    int p=count_less(l,r,x+1);
    return p?kth(l,r,p):0;
}
int next_value(int l,int r,int x)
{
    int p=count_less(l,r,x);
    return p<r-l+1?kth(l,r,p+1):0;
}
int near(int u,int l,int r)
{
    int x=prev_value(l,r,tin[u]);
    int y=next_value(l,r,tin[u]);
    int p=x?lca(u,rev[x]):0;
    int q=y?lca(u,rev[y]):0;
    if(!p)return q;
    if(!q)return p;
    return dep[p]>=dep[q]?p:q;
}
void insert_event(set<int> &q,int p)
{
    auto z=q.lower_bound(p);
    int x=z==q.begin()?0:*prev(z);
    int y=z==q.end()?n+1:*z;
    ins.push_back({x,p,y});
    q.insert(z,p);
}
void build_events()
{
    ins.reserve(static_cast<size_t>(n)*12);
    for(int i=n;i;i--)
    {
        int u=ord[i];
        beg[u]=ins.size();
        ps[u]=son[u]?ps[son[u]]:new set<int>;
        for(int j=head[u];j;j=nxt[j])
        {
            int v=to[j];
            if(fa[v]!=u||v==son[u])continue;
            for(auto k:*ps[v])insert_event(*ps[u],k);
            delete ps[v];
        }
        insert_event(*ps[u],u);
        cnt[u]=ins.size()-beg[u];
    }
    delete ps[1];
}
uint gap(int l,int r,int w)
{
    return l>r?0:mat[li[l]*w+ri[r]];
}
void rebuild()
{
    int m=uc;
    if(!m)return;
    uint sum=0;
    for(int i=0;i<m;i++)
    {
        cx[i]=up[i].l;
        cy[i]=up[i].r;
        sum+=up[i].v;
    }
    sort(cx,cx+m);
    sort(cy,cy+m);
    int h=(int)(unique(cx,cx+m)-cx);
    int z=(int)(unique(cy,cy+m)-cy);
    int w=z+1;
    fill(mat,mat+(h+1)*w,0);
    for(int k=0;k<m;k++)
    {
        int i=(int)(lower_bound(cx,cx+h,up[k].l)-cx);
        int j=(int)(lower_bound(cy,cy+z,up[k].r)-cy)+1;
        mat[i*w+j]+=up[k].v;
    }
    for(int i=h-1;i>=0;i--)
    {
        for(int j=1;j<w;j++)mat[i*w+j]+=mat[(i+1)*w+j]+mat[i*w+j-1]-mat[(i+1)*w+j-1];
    }
    int j=0;
    for(int i=1;i<=n+1;i++)
    {
        while(j<h&&cx[j]<i)j++;
        li[i]=j;
    }
    j=0;
    for(int i=0;i<=n;i++)
    {
        while(j<z&&cy[j]<=i)j++;
        ri[i]=j;
    }
    fill(neg+1,neg+n+1,0);
    for(int i=0;i<m;i++)if(up[i].g!=1)neg[fa[up[i].g]]-=up[i].v;
    for(int i=n;i;i--)
    {
        int u=ord[i];
        uint d=0;
        for(size_t k=beg[u];k<beg[u]+cnt[u];k++)
        {
            auto t=ins[k];
            d-=gap(t.pre+1,t.nxt-1,w);
            d+=gap(t.pre+1,t.pos-1,w);
            d+=gap(t.pos+1,t.nxt-1,w);
        }
        bad[u]=(son[u]?bad[son[u]]:sum)+d;
        uint v=sum-bad[u]+neg[u];
        a[u]+=b[u]*v;
        if(fa[u])neg[fa[u]]+=neg[u];
    }
    for(int i=1;i<=n;i++)
    {
        int u=ord[i];
        s[u]=s[fa[u]]+a[u];
    }
    uc=0;
}
uint query_point(int x)
{
    uint res=a[x];
    for(int i=0;i<uc;i++)
    {
        auto t=up[i];
        if(tin[t.g]<=tin[x]&&tin[x]<=tout[t.g]&&near(x,t.l,t.r)==x)res+=b[x]*t.v;
    }
    return res;
}
uint query_path(int x)
{
    uint res=s[x];
    for(int i=0;i<uc;i++)
    {
        auto t=up[i];
        if(tin[t.g]<=tin[x]&&tin[x]<=tout[t.g])
        {
            int y=near(x,t.l,t.r);
            res+=t.v*(sb[y]-sb[fa[t.g]]);
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    build_tree();
    build_lca();
    build_range();
    build_wavelet();
    build_events();
    uint last=0;
    int cur=0;
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            uint l,r,v;
            cin>>l>>r>>v;
            l^=last;
            r^=last;
            v^=last;
            int x=(int)l,y=(int)r;
            up[uc++]={x,y,range_lca(x,y),v};
        }
        else if(op==2)
        {
            uint x;
            cin>>x;
            x^=last;
            last=query_point((int)x);
            cout<<last<<'\n';
        }
        else if(op==3)
        {
            uint x;
            cin>>x;
            x^=last;
            last=query_path((int)x);
            cout<<last<<'\n';
        }
        if(++cur==B){rebuild();cur=0;}
    }
    return 0;
}