BZOJ 4765 普通计算姬

发表于 | 更新于

Link

Solution

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