翻车笔记_ BZOJ4765 普通计算姬 [分块, 清奇脑回路, 大分块, 翻车]

合理平衡复杂度是手筋

懵逼的 题目

qwq

扯淡的 题解

不会, 抄的题解

来…让我们想一下 树链剖分一次修改的复杂度是$\mathrm O(\lg n)$, 但是查询是$\mathrm O(n)$的

好…那我们就可以平衡复杂度了

考虑一下修改一个点对答案的贡献, 修改一个节点的权值只会对他的祖先造成影响, 我们就可以搞一个区间求和的大分块, 记录最后的ans, 然后搞一个数组g[i][j], 表示第$i$个节点在第$j$个块有几个祖先(包括自己), 这样修改的时候就可以直接sum[i] += g[dq][i] * zh

那么零散的块呢? 总不能搞一个树链剖分吧…

Emmmmm…如果我们不记录子树和, 而是每一次都重新计算呢?

在$dfs$序上搞一个树状数组, 然后每一次都重新计算子树和!

完美!

感觉再给我三辈子我也想不出来_(:з」∠)_

好…让我们想想我们需要些什么…

  • 一个区间修改, 区间查询的块qwq, 用来存储最终的答案
    • 一个数组sum[MAXK], 记录当前块的数字和; 一个单点修改, 区间查询的树状数组b, 建在$dfs$序上, 用来存储每一个节点的子树和
    • ULL cx(int le, int ri):
      • 找到$[le, ri]$间的整块, re += sum[i]
      • 对于所有的零散点, re += cxsum(i)
    • void xg(int wz, ULL zh): 遍历所有的块, sum[i] += zh * g[wz][i], xgsum(ta[wz].begin, zh)
  • 一个数组g[MAXN][MAXK]: g[i][j]用来存储第i个节点在第j个块中的祖先个数(用来记录贡献)
  • 一个结构体ta[MAXN] = {begin, end}, 来搞$dfs$序

沙茶的 代码

注意几个细节:

  • 分块的时候一定要在最后一个块的右边界上加一个和$n$的取$\min$…否则$RE$死你…
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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXK (350 + 5)
#define INF (0x7ffffff)
#define lowbit(x) ((x) & (-(x)))
#define ULL unsigned long long
#define LL long long
#define rint register int
#define cint const int
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct edg
{
int from, to, next;
}tb[MAXN << 1];
struct tnode
{
int begin, end, fa;
}ta[MAXN];
int n, root, tg[MAXN], g[MAXN][MAXK], cnta, cntb, block, le[MAXK], ri[MAXK];
ULL sum[MAXK], b[MAXN];
LL a[MAXN];
inline int belong(int x)
{ return ((x - 1) / block + 1); }
inline ULL cxsum(int x)
{
ULL re = 0;
for (int i = ta[x].end; i; i -= lowbit(i))
re += b[i];
for (int i = ta[x].begin - 1; i; i -= lowbit(i))
re -= b[i];
return re;
}
inline void xgsum(int wz, LL zh)
{
for (int i = wz; i <= n; i += lowbit(i))
b[i] += zh;
}
void dfs(int dq)
{
ta[dq].begin = ++cnta;
xgsum(cnta, a[dq]);
for (int i = 1; i <= le[0]; i++)
g[dq][i] = g[ta[dq].fa][i];
++g[dq][belong(dq)];
for (int i = tg[dq]; i; i = tb[i].next)
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
dfs(tb[i].to);
}
ta[dq].end = cnta;
}
void xg(int wz, LL zh)
{
a[wz] += zh;
for (int i = 1; i <= le[0]; i++)
sum[i] += zh * g[wz][i];
xgsum(ta[wz].begin, zh);
}
ULL cx(int l, int r)
{
ULL re = 0;
int lerk = INF, rigk = -INF;
for (int i = 1; i <= le[0]; i++)
if (le[i] >= l && ri[i] <= r)
{
re += sum[i];
lerk = min(lerk, i), rigk = max(rigk, i);
}
if (lerk >= INF || rigk < 0)
{
for (int i = l; i <= r; i++)
re += cxsum(i);
return re;
}
if (lerk > 1)
for (int i = l; i <= ri[lerk - 1]; i++)
re += cxsum(i);
if (rigk < le[0])
for (int i = le[rigk + 1]; i <= r; i++)
re += cxsum(i);
return re;
}
void init()
{
block = sqrt(n) + 1;
for (int i = 1; i <= n; i += block)
le[++le[0]] = i, ri[++ri[0]] = min(n, i + block - 1);
}
void adn(int from, int to)
{
tb[++cntb].next = tg[from];
tb[cntb].from = from;
tb[cntb].to = to;
tg[from] = cntb;
}
int main()
{
freopen("in.in", "r", stdin);
int q;
scanf("%d%d", &n, &q);
init();
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1, srx, sry; i <= n; i++)
{
scanf("%d%d", &srx, &sry);
if (!srx)
{
root = sry;
continue;
}
adn(srx, sry);
adn(sry, srx);
}
ta[root].fa = root;
dfs(root);
for (int i = 1; i <= le[0]; i++)
for (int j = le[i]; j <= ri[i]; j++)
sum[i] += cxsum(j);
for (int i = 1, sre, srx, sry; i <= q; i++)
{
scanf("%d%d%d", &sre, &srx, &sry);
if (sre == 1)
xg(srx, sry - a[srx]);
else
printf("%llu\n", cx(srx, sry));
}
return 0;
}

By 大傻叉 Cansult