BZOJ 4765 普通计算姬

Link

Solution

\([1..n]\)这个答案序列分块!!为什么我总是想把树分块。。。 想到这,接着就比较好说了。 修改一个点对块的影响,是使得它在块内的祖先的权值都相应变化。块内的祖先个数,可以\(O(n\sqrt n)\)地预处理出来。 这样整块的统计是\(O(\sqrt n)\)的,那么零碎部分的也尽量\(O(\sqrt n)\),那就要求每个点的求值是\(O(1)\)的。显然常见套路树状数组做不到。 那么再用dfs序分块替代树状数组。同样支持区间修改,询问变成\(O(1)\),修改\(O(\sqrt n)\)。总复杂度就是\(O(n\sqrt n)\)了。 # Code

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
#include "lucida"
import copy;
typedef unsigned long long qword;
const int MAXN=1e5+11,MAXB=320;
struct Edge {
int to;Edge *pre;
Edge(int to,Edge *pre):to(to),pre(pre) {}
void *operator new(size_t) {
static Edge *Me=alloc(Edge,MAXN<<1);
return Me++;
}
}*G[MAXN];
void Adde(int f,int t) {
G[f]=new Edge(t,G[f]);
G[t]=new Edge(f,G[t]);
}
//序列分块
int bsz,bs[MAXN],bt[MAXN],bc,bn[MAXN],parCnt[MAXN][MAXB];
qword bAns[MAXB],pref[MAXN];
int64 a[MAXN],mrk[MAXB];
int fa[MAXN],lbd[MAXN],rbd[MAXN],dfs[MAXN],dc;
qword DFS(int pos) {
static int cnt[MAXB];//存储祖先 每块的个数
qword sum=a[pos];
cnt[bn[pos]]++;
dfs[lbd[pos]=++dc]=pos;
copy(cnt+1,cnt+1+bc,parCnt[pos]+1);
for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
int u=e->to;
fa[u]=pos;
sum+=DFS(u);
}
cnt[bn[pos]]--;
bAns[bn[pos]]+=sum;
rbd[pos]=dc;
return sum;
}
void Change(int pos,int64 v) {
for(int b=1;b<=bc;++b) {
bAns[b]+=(v-a[pos])*parCnt[pos][b];
}
int dfn=lbd[pos];
for(int b=bn[dfn]+1;b<=bc;++b) {
mrk[b]+=v-a[pos];
}
for(int i=dfn;i<=bt[bn[dfn]];++i) {
pref[i]+=v-a[pos];
}
a[pos]=v;
}
qword SbtSum(int rt) {
return (pref[rbd[rt]]+mrk[bn[rbd[rt]]])-(pref[lbd[rt]-1]+mrk[bn[lbd[rt]-1]]);
}
qword Query(int l,int r) {
qword res=0;
if(bn[l]==bn[r]) {
for(int i=l;i<=r;++i) {
res+=SbtSum(i);
}
} else {
for(int b=bn[l]+1;b<=bn[r]-1;++b) {
res+=bAns[b];
}
for(int i=l;i<=bt[bn[l]];++i) {
res+=SbtSum(i);
}
for(int i=bs[bn[r]];i<=r;++i) {
res+=SbtSum(i);
}
}
return res;
}
int main() {
// freopen("input","r",stdin);
int n,m;is>>n>>m;
bsz=sqrt(n+0.5);
for(int i=1;i<=n;++i) {
is>>a[i];
bn[i]=(i-1)/bsz+1;
if(bn[i]!=bn[i-1]) {
bs[bn[i]]=i;
bt[bn[i-1]]=i-1;
}
}
bt[bc=bn[n]]=n;
int root;
for(int i=1;i<=n;++i) {
int x,y;is>>x>>y;
if(x) {
Adde(x,y);
} else {
root=y;
}
}
DFS(root);
for(int i=1;i<=n;++i) {
pref[i]=pref[i-1]+a[dfs[i]];
}
for(int i=1;i<=m;++i) {
int op,x,l,r;
int64 v;
is>>op;
if(op==1) {
is>>x>>v;
Change(x,v);
} else {
is>>l>>r;
qword Ans=Query(l,r);
os<<Ans<<'\n';
}
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利