洛谷 5891 Fracture Ray

感觉 bitset 建虚树做法好不靠谱（

有一个结论：q 个 u 到根的路径的并集不会特别多，大概是 8×107 左右。
于是考虑用 bitset 维护走过的结点，然后建出虚树即可。
然后树剖。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
const int N = 8e5;
const int Q = 2e5;
const int S = 1 << 24;
const int W = 6;
const int B = 1 << W;
int n,q,v,rt;
int a[N + 5];
vector<int> key;
unordered_map<int,int> id;
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct s_operation
{
    int op,u,p;
} opt[Q + 5];
struct Bitset
{
    unsigned long long a[S + 5];
    inline void set(int x)
    {
        a[x >> W] |= 1ULL << (x & B - 1);
    }
    inline int test(int x)
    {
        return (a[x >> W] >> (x & B - 1)) & 1;
    }
    inline void reset()
    {
        memset(a,0,sizeof a);
    }
} vis;
namespace SEG
{
    #define ls (p << 1)
    #define rs (ls | 1)
    long long sum[N + 5];
    struct node
    {
        long long sum,tag;
    } seg[(N << 2) + 5];
    void update(int l,int r,int k,int p,int tl,int tr)
    {
        seg[p].sum += (long long)k * (sum[min(tr,r)] - sum[max(tl,l) - 1]);
        if(l <= tl && tr <= r)
            return (void)(seg[p].tag += k);
        int mid = tl + tr >> 1;
        l <= mid && (update(l,r,k,ls,tl,mid),1);
        r > mid && (update(l,r,k,rs,mid + 1,tr),1);
    }
    long long query(int l,int r,int p,int tl,int tr)
    {
        if(l <= tl && tr <= r)
            return seg[p].sum;
        int mid = tl + tr >> 1;
        long long ret = seg[p].tag * (sum[min(tr,r)] - sum[max(tl,l) - 1]);
        l <= mid && (ret += query(l,r,ls,tl,mid));
        r > mid && (ret += query(l,r,rs,mid + 1,tr));
        return ret;
    }
}
namespace HLD
{
    int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],rk[N + 5];
    void dfs1(int p)
    {
        sz[p] = 1;
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
                fa[to[i]] = p,dep[to[i]] = dep[p] + 1,
                dfs1(to[i]),
                sz[p] += sz[to[i]],
                son[p] = max(son[p],to[i],[](int x,int y){
                    return sz[x] < sz[y];
                });
    }
    void dfs2(int p)
    {
        static int tot = 0;
        rk[id[p] = ++tot] = p;
        if(son[p])
            top[son[p]] = top[p],dfs2(son[p]);
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p] && to[i] ^ son[p])
                top[to[i]] = to[i],dfs2(to[i]);
    }
    void update(int p,int k)
    {
        while(p)
            SEG::update(id[top[p]],id[p],k,1,1,n),p = fa[top[p]];
    }
    long long query(int p)
    {
        long long ret = 0;
        while(p)
            ret += SEG::query(id[top[p]],id[p],1,1,n),p = fa[top[p]];
        return ret;
    }
}
int main()
{
    scanf("%d%d",&q,&v),rt = v + 1;
    for(register int i = 1,x;i <= q;++i)
    {
        scanf("%d%d",&opt[i].op,&opt[i].u),opt[i].op == 1 && scanf("%d",&opt[i].p),
        key.push_back(x = opt[i].u);
        for(;x <= v && !vis.test(x);x += __builtin_popcount(x))
            vis.set(x);
        x <= v && (key.push_back(x),1);
    }
    sort(key.begin(),key.end(),greater<int>()),vis.reset();
    for(auto u : key)
    {
        if(!id.count(u))
            id[u] = ++n;
        if(vis.test(u))
            continue;
        register int x = u;
        for(;x <= v && !vis.test(x);x += __builtin_popcount(x))
            vis.set(x),++a[id[u]];
        x = min(x,rt);
        if(!id.count(x))
            id[x] = ++n;
        add(id[x],id[u]);
    }
    rt = id[rt],
    HLD::dep[rt] = 1,HLD::top[rt] = rt,HLD::dfs1(rt),HLD::dfs2(rt);
    for(register int i = 1;i <= n;++i)
        SEG::sum[i] = SEG::sum[i - 1] + a[HLD::rk[i]];
    for(register int i = 1;i <= q;++i)
        opt[i].op == 1 ? (HLD::update(id[opt[i].u],opt[i].p),1) : printf("%lld\n",HLD::query(id[opt[i].u]));
}