感觉 bitset 建虚树做法好不靠谱（
有一个结论：\(q\) 个 \(u\) 到根的路径的并集不会特别多，大概是 \(8\times 10^7\) 左右。
于是考虑用 bitset 维护走过的结点，然后建出虚树即可。
然后树剖。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
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
{
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]));
}