铃铛计数问题 (根号重构,主席树)

题目链接

题目大意

​ 给一棵树,点带权,$size(i)$表示$i$号点子树中节点的权值和,多组询问修改点权或求$\sum_{i=l}^r size(i)$。

题目解法

​ 如果没有修改操作,可以一次dfs预处理子树大小然后前缀和即可。

​ 考虑对于当前询问操作$[l, r]$之前的一次修改操作$[u, \Delta w]$,它对当前答案的贡献是容易统计的,即为$u$到根的路径中编号在$[l,r]$中的点的个数,可以采用主席树求出。

​ 考虑根号重构,当之前未被处理的修改操作大于$B$时,重新dfs整棵树,预处理前缀和,并将之前所有操作标记为已处理。每次询问时首先前缀和求出已经被处理的修改操作的答案,然后对于之前未被处理的操作主席树统计贡献。复杂度为$O(qBlogn+qn/B)$。认为$n,q$同级,取$B=\frac{\sqrt{nlogn}}{logn}$可以得到$O(n\sqrt{nlogn})$的垃圾做法。因为常数差异实际块大小与理论最优略有不同,适当卡常并调整块大小可以通过本题。

代码

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
#include <bits/stdc++.h>
#define maxn 100005
#define ll long long
int n,q,opt,l,r,p[maxn],v[maxn],cnt=0,tail=0,head[maxn]={0},root[maxn],
rt,w[maxn],tot[maxn<<5]={0},ch[maxn<<5][2]={0},rank[maxn]={0},fa[maxn]={0};
unsigned ll sum[maxn]={0},size[maxn]={0},dfn[maxn]={0},idx=0;
struct edge {
int v,next;
}edges[maxn<<1];
int cmp(int a,int b) {return dfn[a]>dfn[b];}
inline int read() {
int x=0;char c=getchar();
while (c>'9'||c<'0') c=getchar();
while ('0'<=c&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x;
}
inline void add_edge(int u,int v) {
edges[++tail].v=v;
edges[tail].next=head[u];
head[u]=tail;
}

void dfs1(int u,int f) {
fa[u]=f;dfn[u]=++idx;
for (register int i=head[u];i;i=edges[i].next) {
int v=edges[i].v;
if (v!=f) {dfs1(v,u);}
}
}

void rebuild() {
std::memset(size,0,sizeof(size));
for (register int i=1;i<=n;++i) {
size[rank[i]]+=w[rank[i]];size[fa[rank[i]]]+=size[rank[i]];
}
for (register int i=1;i<=n;++i) sum[i]=sum[i-1]+size[i];
cnt=0;
}

int insert(int l,int r,int p,int rt) { //debug
int nrt=++tail;
ch[nrt][0]=ch[rt][0];ch[nrt][1]=ch[rt][1]; tot[nrt]=tot[rt]+1;
if (l==r) return nrt;
int mid=(l+r)>>1;
if (p<=mid) ch[nrt][0]=insert(l,mid,p,ch[rt][0]);
else ch[nrt][1]=insert(mid+1,r,p,ch[rt][1]);
return nrt;
}

void dfs2(int u,int f) {
root[u]=insert(1,n,u,root[f]);
for (register int i=head[u];i;i=edges[i].next) {
int v=edges[i].v;
if (v!=f) dfs2(v,u);
}
}

int query(int l,int r,int L,int R,int rt) {
if (l>R||r<L||!rt) return 0;
if (l<=L&&R<=r) return tot[rt];
return query(l,r,L,(L+R)>>1,ch[rt][0])+query(l,r,((L+R)>>1)+1,R,ch[rt][1]);
}

int main() {
scanf("%d%d",&n,&q);
int size=(int)std::sqrt(q)*0.85;
for (int i=1;i<=n;++i) scanf("%d",&w[i]);
for (int i=1;i<=n;++i) {
int u,v; rank[i]=i;
u=read();v=read();
if (!u||!v) rt=u+v;
else {add_edge(u,v);add_edge(v,u);}
} dfs2(rt,0);dfs1(rt,0);
std::sort(rank+1,rank+n+1,cmp);
rebuild();
for (int i=1;i<=q;++i) {
opt=read();l=read();r=read();
if (opt==1) {
p[++cnt]=l;v[cnt]=r-w[l]; w[l]=r;
} else {
unsigned ll ans=0;
ans=sum[r]-sum[l-1];
for (register int i=1;i<=cnt;++i) ans+=(ll)query(l,r,1,n,root[p[i]])*(ll)v[i];
printf("%lld\n",ans);
} if (i%size==0) rebuild();
}
return 0;
}