Luogu

分析

对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。

然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。

但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f$，那么原树上将 $u\to f$ 这条链（不包括 $f$）加上 $w$ 等价于虚树上将 $u$ 加上 $cnt_x\times w$。

那么就可以直接对虚树树剖+线段树维护了。现在的问题主要在于如何建出虚树。

首先想办法找到所有在虚树中的点。显然每个操作中的点都在虚树中；剩下的部分可以开一个大小为 $2^{30}$ 的 std::bitset 来记录每个点是否到过，对于每个操作中的点，暴力向上跳父亲直到当前点之前到过或 $>v$，则最后跳到的这个点也在虚树中。

然后我们要确定每个点在虚树上的父亲。注意到某个点的祖先一定比它大，所以我们可以把这些点从大到小排序后再依次拿出来做上面的过程，最后跳到的点即为虚树上的父亲。

这样子看似很暴力，但是实际上访问到的点数不多，所以是可以过的。

如果被卡常了可以手写 std::bitset。然而应该只有我被卡常了 /dk

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define popcount __builtin_popcount
#pragma GCC optimize("Ofast,no-stack-protector,fast-math,unroll-loops")
using namespace std;
typedef long long ll;

namespace IO {
    const int SIZE=1<<21;
    char ibuf[SIZE|1],*iS,*iT,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1;
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    char getc() {
        if (iS==iT) {
            iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin);
            if (iS==iT) return EOF;
        }
        return *iS++;
    }
    void putc(char x) { *oS++=x; if (oS==oT) flush(); }
    int read() {
        int X=0,w=1; char c=getc();
        while (c<'0'||c>'9') { if (c=='-') w=-1; c=getc(); }
        while (c>='0'&&c<='9') X=X*10+c-'0',c=getc();
        return X*w;
    }
    void write(ll x) {
        static char sta[65]; int top=0;
        if (!x) putc('0');
        if (x<0) putc('-'),x=-x;
        while (x) sta[++top]=x%10+'0',x/=10;
        while (top) putc(sta[top--]);
    }
    struct flusher { ~flusher() { flush(); } } io_flusher;
}
using IO::getc;
using IO::putc;
using IO::read;
using IO::write;

const int N=800000+10;

int Q,lim,rt,cnt[N];
struct query { int op,u,w; } q[N];
unsigned bit[1<<25|1];
bool get(int x) { return (bit[x>>5]>>(x&31))&1; }
vector<int> v,E[N];
unordered_map<int,int> id; int tot=0;

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],pos[N],tim=0;
void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (int v:E[u]) {
        if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,pos[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (int v:E[u])
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}

namespace T {
#define ls (o<<1)
#define rs (o<<1|1)
    ll sumv[N<<2],sumtag[N<<2],addv[N<<2];
    void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
    void pushdown(int o) {
        if (addv[o]) {
            addv[ls]+=addv[o],sumv[ls]+=sumtag[ls]*addv[o];
            addv[rs]+=addv[o],sumv[rs]+=sumtag[rs]*addv[o];
            addv[o]=0;
        }
    }
    void build(int o,int l,int r) {
        if (l==r) { sumtag[o]=cnt[pos[l]]; return; }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        sumtag[o]=sumtag[ls]+sumtag[rs];
    }
    void modify(int o,int l,int r,int ql,int qr,int w) {
        if (ql<=l&&r<=qr) { addv[o]+=w,sumv[o]+=sumtag[o]*w; return; }
        int mid=(l+r)>>1; pushdown(o);
        if (ql<=mid) modify(ls,l,mid,ql,qr,w);
        if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
        pushup(o);
    }
    ll query(int o,int l,int  r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sumv[o];
        int mid=(l+r)>>1; ll res=0; pushdown(o);
        if (ql<=mid) res+=query(ls,l,mid,ql,qr);
        if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
        pushup(o); return res;
    }
#undef ls
#undef rs
}

void modify(int u,int w) {
    while (top[u]!=rt) {
        T::modify(1,1,tot,dfn[top[u]],dfn[u],w);
        u=fa[top[u]];
    }
    T::modify(1,1,tot,1,dfn[u],w);
}
ll query(int u) {
    ll res=0;
    while (top[u]!=rt) {
        res+=T::query(1,1,tot,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    return res+T::query(1,1,tot,1,dfn[u]);
}

int main() {
    Q=read(),lim=read();
    for (int i=1;i<=Q;++i) {
        q[i].op=read(),q[i].u=read();
        if (q[i].op==1) q[i].w=read();
        int u=q[i].u; v.emplace_back(u);
        for (;u<=lim&&!get(u);u+=popcount(u)) bit[u>>5]|=1u<<(u&31);
        if (u<=lim) v.emplace_back(u);
    }
    sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
    memset(bit,0,sizeof(bit));
    for (int i=v.size()-1;~i;--i) {
        int u=v[i]; if (!id[u]) id[u]=++tot;
        int f=u;
        for (;f<=lim&&!get(f);f+=popcount(f)) bit[f>>5]|=1u<<(f&31),++cnt[id[u]];
        if (f>lim) f=lim+1;
        if (!id[f]) id[f]=++tot;
        E[id[f]].emplace_back(id[u]);
    }
    rt=id[lim+1]; dfs1(rt,0),dfs2(rt,rt); T::build(1,1,tot);
    for (int i=1;i<=Q;++i) {
        if (q[i].op==1) modify(id[q[i].u],q[i].w);
        else write(query(id[q[i].u])),putc('\n');
    }
    return 0;
}