题解 P5891 【Fracture Ray】

· · 题解

可能更好的体验

考虑对每个 u，暴力往上跳，这样跳过的不同节点的总数不会非常多，平均下来大概在 7\times 10^7\sim 8\times 10^7 这样子。目前似乎无法将其卡掉。

然而实际上访问的只有 q 个不同的节点，所以这个实际上的森林会有非常多的地方是一条单链。为了方便，可以将森林加一个根节点转为一棵树。

我们考虑求出这棵树的虚树，它有 O(q) 个节点。然后求出 v_x 表示节点 x 到其虚树上父亲在原树的路径中的节点个数（不包括父亲）。那么对 x 及其子树中到根路径加 p 的操作，我们就可以把 x 到其虚树上的父亲的这段直接在虚树节点 x 上考虑，即直接在 x 上加 p\cdot v_x。查询的时候也只需查询这个点在虚树上到根路径上的点的点权和即可。

由于 v 数组是唯一确定的，所以链加链和可以直接使用树链剖分+线段树维护，或者使用 LCT 等数据结构即可维护。

然后关键就是建出这棵虚树。我们用一个 2^{30} 的 bitset 记录每个点是否被访问过，然后对询问离线，对每个 u 都暴力往上跳，找到第一个被访问过的点（或者超过 V），并将沿途上的点标记为访问过。那么每个 u 开始和结尾的点就是可能出现在虚树中的点。求 v_x 和虚树上的连边，可以通过将能出现在虚树上的点排序后，从大到小再暴力往上跳一遍，遇到访问过的节点停止。

根据上面“不同的节点总数不会非常多”的结论，上面的做法是不会超时的。

由于 2^{30} 的 bitset 会 CMLE，所以需要手写一个简单的 bitset。

数据结构维护部分的复杂度为 O(q\log^2 q) 或 O(q\log q)。空间复杂度 O(q+V)。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
#define popcnt __builtin_popcount
const int N=8e5+6;
unsigned b[1<<25|1];
map<int,int>id;
int m,V,tot,head[N],fa[N],val[N],rt,sz[N],son[N],top[N],dep[N],dfn[N],idx,cnt,vval[N];
int rsc[N<<2];
LL tag[N<<2],d[N<<2];
struct edge{
    int to,nxt;
}e[N];
struct que{
    int op,u,p;
}q[N];
vector<int>vec;
inline bool test(const int&x){return b[x>>5]>>(x&31)&1;}
void dfs(int now){
    sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt){
        dep[e[i].to]=dep[now]+1,dfs(e[i].to);
        sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    dfn[now]=++idx;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=son[now])dfs2(top[e[i].to]=e[i].to);
}
void build(int l,int r,int o){
    if(l==r)rsc[o]=vval[l];else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        rsc[o]=rsc[o<<1]+rsc[o<<1|1];
    }
}
inline void pushdown(int o){
    LL&x=tag[o];
    tag[o<<1]+=x,tag[o<<1|1]+=x;
    d[o<<1]+=x*rsc[o<<1],d[o<<1|1]+=x*rsc[o<<1|1],x=0;
}
void add(int l,int r,int o,const int&L,const int&R,const int&x){
    if(L<=l&&r<=R){
        tag[o]+=x;
        d[o]+=(LL)rsc[o]*x;
    }else{
        pushdown(o);
        const int mid=l+r>>1;
        if(L<=mid)add(l,mid,o<<1,L,R,x);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,x);
        d[o]=d[o<<1]+d[o<<1|1];
    }
}
LL query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return d[o];
    pushdown(o);
    const int mid=l+r>>1;
    LL res=0;
    if(L<=mid)res=query(l,mid,o<<1,L,R);
    if(mid<R)res+=query(mid+1,r,o<<1|1,L,R);
    return res;
}
void Add(int x,int v){
    while(top[x]!=rt){
        add(1,idx,1,dfn[top[x]],dfn[x],v);
        x=fa[top[x]];
    }
    add(1,idx,1,1,dfn[x],v);
}
LL ask(int x){
    LL res=0;
    while(top[x]!=rt){
        res+=query(1,idx,1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    res+=query(1,idx,1,1,dfn[x]);
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>V;
    for(int i=1;i<=m;++i){
        cin>>q[i].op>>q[i].u;
        if(q[i].op==1)cin>>q[i].p;
        int x=q[i].u;
        vec.push_back(x);
        for(;x<=V&&!test(x);x+=popcnt(x))b[x>>5]|=1u<<(x&31);
        if(x<=V)vec.push_back(x);
    }
    sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());
    memset(b,0,sizeof b);
    for(int i=(int)vec.size()-1;~i;--i){
        int x=vec[i];
        if(!id.count(x))id[x]=++tot;
        int pid=id[x];
        int&ct=val[pid];
        if(test(x))continue;
        ct=0;
        for(;x<=V&&!test(x);x+=popcnt(x))b[x>>5]|=1u<<(x&31),++ct;
        if(x>V)x=V+1;
        if(!id.count(x))id[x]=++tot;
        int nid=id[x];
        fa[pid]=nid;
        e[++cnt]=(edge){pid,head[nid]},head[nid]=cnt;
    }
    rt=id[V+1];
    val[rt]=0;
    top[rt]=rt;
    dfs(rt),dfs2(rt);
    for(int i=1;i<=idx;++i)vval[dfn[i]]=val[i];
    build(1,idx,1);
    for(int i=1;i<=m;++i)
    if(q[i].op==1)Add(id[q[i].u],q[i].p);
    else cout<<ask(id[q[i].u])<<'\n';
    return 0;
}