2D0y a。
结论拍脸。
显然如果 \(i\to i+\text{popcount(i)}\) 这样连边的话，连出来是一个森林。
结论就是 \(q\) 个 \(u\) 到根的路径的点，去重后的个数不超过 \(8\times 10^7\)。
然后 bitset 维护所有走过的点，建出虚树，点数就变成 \(O(q)\) 的了。
然后树剖线段树就能在 \(O(q\log^2 q)\) 的时间内解决。
要手写 bitset。
// Problem: P5891 Fracture Ray
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5891
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
// #define FILE
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Med;
const int N = 5e6 + 500;
const int M = 3.5e7 + 350;
map<int, int> pid;
vector<tu> qr;
vector<int> p, g[N];
int q, m, rt, tot, dfc;
int fa[N], sz[N], dep[N], son[N], id[N], top[N];
ll s[N], vl[N];
struct BIT {
unsigned int f[M];
void reset() { memset(f, 0, sizeof(f)); }
void set(int x) { f[x >> 5] |= (1ll << (x & 31)); }
int test(int x) { return (f[x >> 5] >> (x & 31)) & 1; }
} B;
struct SEG {
ll tr[N << 2], lz[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void ptg(int l, int r, ll c, int x) { tr[x] += 1ll * (s[r] - s[l - 1]) * c, lz[x] += c; }
void pdn(int l, int r, int x) {
if (!lz[x]) return;
ptg(l, mid, lz[x], ls), ptg(mid + 1, r, lz[x], rs);
lz[x] = 0;
}
void upd(int l, int r, int s, int t, ll c, int x) {
if (t < s) return;
if (s <= l && r <= t) return ptg(l, r, c, x);
pdn(l, r, x);
if (s <= mid) upd(l, mid, s, t, c, ls);
if (t > mid) upd(mid + 1, r, s, t, c, rs);
tr[x] = tr[ls] + tr[rs];
}
ll qry(int l, int r, int s, int t, int x) {
if (t < s) return 0;
if (s <= l && r <= t) return tr[x];
pdn(l, r, x); ll res = 0;
if (s <= mid) res += qry(l, mid, s, t, ls);
if (t > mid) res += qry(mid + 1, r, s, t, rs);
return res;
}
} T;
#define pct(x) __builtin_popcountll(x)
#define gt(x, y) get<y>(x)
int gid(int u) {
if (!pid[u]) pid[u] = ++tot;
return pid[u];
}
void dfs1(int u) {
sz[u] = 1, dep[u] = dep[fa[u]] + 1;
for (int v : g[u]) {
dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int pr) {
top[u] = pr, s[id[u] = ++dfc] = vl[u];
if (son[u]) dfs2(son[u], pr);
for (int v : g[u]) {
if (v == son[u]) continue;
dfs2(v, v);
}
}
void upd(int u, int c) {
while (u) {
T.upd(1, dfc, id[top[u]], id[u], c, 1);
u = fa[top[u]];
}
}
ll qry(int u) {
ll res = 0;
while (u) {
res += T.qry(1, dfc, id[top[u]], id[u], 1);
u = fa[top[u]];
}
return res;
}
void solve() {
cin >> q >> m;
for (int i = 1, op, u, w; i <= q; i++) {
cin >> op >> u;
if (op == 1) cin >> w, qr.pb(mt(op, u, w));
else qr.pb(mt(op, u, 0));
p.pb(u);
for (; u <= m && !B.test(u); u += pct(u)) B.set(u);
if (u <= m) p.pb(u);
}
p.pb(m + 1);
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
reverse(p.begin(), p.end()), B.reset();
for (int u : p) {
int iu = gid(u), ifa;
if (u == m + 1) continue;
for (; u <= m && !B.test(u); u += pct(u))
vl[iu]++, B.set(u);
if (u <= m) ifa = gid(u);
else ifa = gid(m + 1);
if (ifa == iu) ifa = gid(m + 1);
g[ifa].pb(iu), fa[iu] = ifa;
}
rt = gid(m + 1);
for (int i = 1; i <= tot; i++)
if (i != rt && !fa[i])
g[rt].pb(i), fa[i] = rt;
dfs1(rt), dfs2(rt, rt);
for (int i = 1; i <= dfc; i++)
s[i] += s[i - 1];
for (tu p : qr) {
if (gt(p, 0) == 1) upd(gid(gt(p, 1)), gt(p, 2));
else cout << qry(gid(gt(p, 1))) << '\n';
}
}
bool Mbe;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Med - &Mbe) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("A.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}