发表更新ICPC/CCPC / Contests / 其他9 分钟读完 (大约1290个字)

2020杭电多校（第九场）

比赛链接

1001 Tree

（原本以为一定是最深的节点往根节点连边，但是不一定，因为贡献里还有子树大小这玩意儿。）

我们先计算出原树的答案。连边一定是从叶节点到根节点连边，连上后，那个叶节点的所有祖先节点都会给答案额外的贡献：$n$ 减去该节点子树大小。所以设 $f(i)$ 表示第 $i$ 个节点及其祖先对答案总的额外贡献，那么取最大即可。

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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 500005;

int T, n, fa[N];
vi edge[N];

LL ans;
LL sz[N], f[N];
void dfs(int x, LL d){
	sz[x] = 1;
	for(auto &to : edge[x])	dfs(to, d+1), sz[x] += sz[to];
	ans += sz[x];
}

LL mx;
void dfs(int x){
	f[x] = f[fa[x]] + n - sz[x];
	mx = max(mx, f[x]);
	for(auto &to : edge[x])	dfs(to);
}

inline void initCASES(){
	ans = mx = 0;
	for(int i = 1; i <= n; i++){
		sz[i] = 0, fa[i] = 0;
		edge[i].clear();
	}
}

int main(){
	for(read(T); T; T--){
		read(n);
		initCASES();
		for(int i = 2; i <= n; i++){
			read(fa[i]);
			edge[fa[i]].pb(i);
		}
		dfs(1, 1);
		dfs(1);
		printf("%lld\n", ans + mx);
	}
	return 0;
}

1002 Absolute Math

队友搞的，先放着占坑。

1003 Slime and Stones

题解说：

通过找规律可得，所有的必败态为 $\left(\left\lfloor\frac{m(1-k+\sqrt{k^2+2k+5})}{2}\right\rfloor,\left\lfloor\frac{m(3+k+\sqrt{k^2+2k+5})}{2}\right\rfloor\right)$.

真是个骨骼清奇的规律啊……（别问我，我没看这题，我啥也不知道……）

1007 Game

写个平衡树模拟即可。

（好久没写平衡树了，有点手生……呃……）

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200005;
const LL INF = 1e16;

int n;
LL b[N];

struct Splay{
	int fa, son[2], size;
	LL val, sum, mn;
	void init(){
		fa = son[0] = son[1] = size = 0;
		val = sum = mn = 0;
	}
}tr[N];
#define which(x,fa) (tr[fa].son[1] == x)
int tot = 0, root = 0;
inline void pushup(int x){
	if(x){
		tr[x].size = 1, tr[x].sum = tr[x].mn = tr[x].val;
		if(tr[x].son[0]){
			tr[x].size += tr[tr[x].son[0]].size;
			tr[x].sum += tr[tr[x].son[0]].sum;
			tr[x].mn = min(tr[tr[x].son[0]].mn, tr[x].mn);
		}
		if(tr[x].son[1]){
			tr[x].size += tr[tr[x].son[1]].size;
			tr[x].sum += tr[tr[x].son[1]].sum;
			tr[x].mn = min(tr[tr[x].son[1]].mn, tr[x].mn);
		}
	}
}
inline void rotate(int x, int dir){ // dir == 0: left, dir == 1: right
	int y = tr[x].fa, z = tr[y].fa, B = tr[x].son[dir];
	tr[z].son[which(y,z)] = x; tr[x].fa = z;
	tr[x].son[dir] = y; tr[y].fa = x;
	tr[y].son[dir^1] = B; tr[B].fa = y;
	pushup(y); pushup(x);
}
inline void splay(int x, int goal){ // rotate x to the son of goal
	if(x == goal)    return;
	while(tr[x].fa != goal){
		int y = tr[x].fa, z = tr[y].fa, dir1 = which(x,y)^1, dir2 = which(y,z)^1;
		if(z == goal)	rotate(x, dir1);
		else{
			if(dir1 == dir2)	rotate(y, dir2);
			else	rotate(x, dir1);
			rotate(x, dir2);
		}
	}
	if(goal == 0)	root = x;
}
inline int selectNode(int x){ // return id of x'th node on the tree
	int now = root;
	while(tr[tr[now].son[0]].size + 1 != x){
		if(tr[tr[now].son[0]].size + 1 > x)
			now = tr[now].son[0];
		else{
			x -= tr[tr[now].son[0]].size + 1;
			now = tr[now].son[1];
		}
	}
	return now;
}

inline int findlast(int x, LL k){
	// find the last node whose val < k in 2nd ~ xth node on the tree
	splay(selectNode(1), 0);
	splay(selectNode(x+1), root);
	int now = tr[tr[root].son[1]].son[0];
	int rk = 1;
	if(tr[now].mn >= k)    return -1;
	while(now && tr[now].mn < k){
		if(tr[now].son[1] && tr[tr[now].son[1]].mn < k)
			rk += tr[tr[now].son[0]].size + 1, now = tr[now].son[1];
		else if(tr[now].val < k){ rk += tr[tr[now].son[0]].size + 1; break; }
		else if(tr[now].son[0] && tr[tr[now].son[0]].mn < k)
			now = tr[now].son[0];
	}
	return rk; // rk: this node is rk'th node on the tree
}
inline LL getSum(int l, int r){
	// return the sum of nodes from l'th to r'th node on the tree
	splay(selectNode(l-1), 0);
	splay(selectNode(r+1), root);
	int now = tr[tr[root].son[1]].son[0];
	return tr[now].sum;
}
inline int del(int x){ // delete the x'th node on the tree
	splay(selectNode(x-1), 0);
	splay(selectNode(x+1), root);
	int now = tr[tr[root].son[1]].son[0];
	tr[tr[root].son[1]].son[0] = 0;
	tr[now].fa = tr[now].size = 0;
	tr[now].son[0] = tr[now].son[1] = 0;
	tr[now].val = tr[now].sum = tr[now].mn = 0;
	pushup(tr[root].son[1]), pushup(root);
	return now;
}
inline void insert(int x, LL val, int id){
	// insert val as the x'th node on the tree, using id as its id
	splay(selectNode(x-1), 0);
	splay(selectNode(x), root);
	tr[tr[root].son[1]].son[0] = id;
	tr[id].fa = tr[root].son[1];
	tr[id].son[0] = tr[id].son[1] = 0;
	tr[id].size = 1;
	tr[id].val = tr[id].sum = tr[id].mn = val;
	pushup(tr[root].son[1]), pushup(root);
}

int build(int l, int r, int fa){
	if(l > r)	return 0;
	int id = ++tot;
	tr[id].fa = fa, tr[id].size = 1;
	int mid = (l + r) >> 1;
	tr[id].val = tr[id].sum = tr[id].mn = b[mid];
	tr[id].son[0] = build(l, mid - 1, id);
	tr[id].son[1] = build(mid + 1, r, id);
	pushup(id);
	return id;
}
bool first = false;
void print(int x){
	if(tr[x].son[0])	print(tr[x].son[0]);
	if(tr[x].val != -INF && tr[x].val != INF){
		if(!first)	printf("%lld", tr[x].val), first = true;
		else	printf(" %lld", tr[x].val);
	}
	if(tr[x].son[1])	print(tr[x].son[1]);
}

inline void init(){
	tot = root = 0;
	for(int i = 1; i <= n + 2; i++)	tr[i].init();
	first = false;
}

int main(){
	int T; for(scanf("%d", &T); T; T--){
		int q; scanf("%d%d", &n, &q);
		init();
		b[0] = -INF, b[n+1] = INF;
		for(int i = 1; i <= n; i++)	scanf("%lld", &b[i]);
		root = build(0, n + 1, 0);
		while(q--){
			int opt, x; LL y;
			scanf("%d", &opt);
			if(opt == 1){
				scanf("%d%lld", &x, &y); x++;
				if(y > tr[selectNode(x)].val){ puts("0"); continue; }
				int pos = findlast(x, y);
				if(pos == -1){ puts("0"); continue; }
				printf("%lld\n", getSum(pos+1, x) - 1ll*(y-1)*(x-pos));
				LL newVal = tr[selectNode(pos+1)].val - y + 1 + tr[selectNode(pos)].val;
				int id = del(pos);
				insert(pos, newVal, id);
				id = del(pos+1);
				insert(x, y-1, id);
			}
			else{
				scanf("%d", &x); x++;
				printf("%lld\n", tr[selectNode(x)].val);
			}
		}
		print(root);
		puts("");
	}
	return 0;
}

2020杭电多校（第九场）

http://xyfjason.github.io/blog-xcpc/2020/08/18/2020杭电多校（第九场）/

作者

xyfJASON

发布于

2020-08-18

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×