本场专题链接：https://vjudge.net/contest/421033

A - 敌兵布阵

题意

维护一个数组，要求可以进行高效的单点增减和区间查询的功能。

分析

虽然说线段树可以做，但这题完全在树状数组能力范围内了。为了避免这篇题解全是线段树模板，还是用树状数组写吧~

代码

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
#include <bits/stdc++.h>
const int maxn = 50005;
using namespace std;
int a[maxn] = {0}, c[maxn] = {0};
int lowbit(int x){
	return x & (-x);
}
int n;
void cal(int i, int s){
	while(i <= n){
		c[i] += s;
		i += lowbit(i);
	}
	return;
}
int query(int x){
	int ans = 0;
	if(x <= 0 || x > n) return 0;
	for(int i = x; i > 0; i -= lowbit(i)){
		ans += c[i];
	}
	return ans;
}
int main()
{
	int t;
	int kase = 1;
	scanf("%d", &t);
	while(t--){
		memset(a, 0, sizeof(a));
		memset(c, 0, sizeof(c));
		printf("Case %d:\n", kase++);
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			scanf("%d", &a[i]);
			cal(i, a[i]);
		}
		char s[50];
		int l, r;
		while(~scanf("%s", &s)){
			if(s[0] == 'E') break;
			else if(s[0] == 'Q'){
				scanf("%d%d", &l, &r);
				printf("%d\n", query(r) - query(l - 1));
			}
			else if(s[0] == 'A'){
				scanf("%d%d", &l, &r);
				cal(l, r);
			}
			else if(s[0] == 'S'){
				scanf("%d%d", &l, &r);
				cal(l, -r);
			}
		}
	}
	return 0;
}

B - I Hate It

题意

维护数组，要求能进行区间最大值查询和单点修改。

分析

虽然说树状数组仍然能做，不过要加的东西就多了点了。这个时候反过来，倒不如直接上线段树。

PS：本专题依旧是现学现做，故这里的线段树是我抄的模板（最大值查询是自己写的），实际上很多函数没有调用哈

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int num[maxn];
int n;
struct node{
	int l, r, sum, lazy, mx;
	node(){
		l = r = sum = lazy = mx =  0;
	}
}a[5 * maxn];
inline void update(int k){
	a[k].sum = a[k * 2].sum + a[k * 2 + 1].sum;
	a[k].mx = max(a[k * 2].mx, a[k * 2 + 1].mx);
}
//建立线段树
void build(int k, int l, int r){
	a[k].l = l, a[k].r = r;
	if(l == r){
		a[k].sum = num[l];
		a[k].mx = num[l];
		return;
	}
	int mid = l + (r - l) / 2;
	build(k * 2, l, mid);
	build(k * 2 + 1, mid + 1, r);
	update(k);
}
//单点修改 
void change(int k, int x, int y)//当前节点，要修改的下标，要修改成的数字
{
	if(a[k].l == a[k].r){
		a[k].sum = y;
		a[k].mx = y;
		return;//查到叶子节点，修改. 
	}
	int mid = (a[k].l + a[k].r) / 2;//计算下一层子区间的左右边界
	if(x <= mid) change(k * 2, x, y);
	else change(k * 2 + 1, x, y);
	update(k);//递归回来要修改k的值 
}
//区间修改 
void segChange(int k, int l, int r, int x){
	if(a[k].l == l && a[k].r == r){
		a[k].sum += (r - l + 1) * x;
		a[k].lazy += x;//lazy在修改时只需要修改一个区间，而查询时顺带接着修改即可. 
		return;
	}
	int mid = (a[k].l + a[k].r) / 2;
	if(r <= mid) segChange(2 * k, l, r, x);
	else if(l > mid) segChange(2 * k + 1, l, r, x);
	else{
		segChange(2 * k, l, mid, x);
		segChange(2 * k + 1, mid + 1, r, x);
	}
	update(k);
}
//传递lazy 
void pushdown(int k)
{
	if(a[k].l == a[k].r){
		a[k].lazy = 0;
		return;
	}
	//给子节点赋值 
	a[2 * k].sum += (a[k * 2].r - a[k * 2].l + 1) * a[k].lazy;
	a[k * 2 + 1].sum += (a[k * 2 + 1].r - a[k * 2 + 1].l + 1) * a[k].lazy;
	
	//下传lazy 
	a[k * 2].lazy += a[k].lazy;
	a[k * 2 + 1].lazy += a[k].lazy;
	a[k].lazy = 0;
}
//区间和查询 
int query(int k, int l, int r){
	if(a[k].lazy) pushdown(k);
	if(a[k].l == l && a[k].r == r) return a[k].sum;//找到区间
	int mid = (a[k].l + a[k].r) / 2;
	if(r <= mid) return query(k * 2, l, r);
	if(l > mid) return query(k * 2 + 1, l, r);
	return query(k * 2, l, mid) + query(k * 2 + 1, mid + 1, r); 
}
//区间最值查询 
int queryMax(int k, int l, int r){
	if(a[k].l == l && a[k].r == r) return a[k].mx;//找到区间
	int mid = (a[k].l + a[k].r) / 2;
	if(r <= mid) return queryMax(k * 2, l, r);
	if(l > mid) return queryMax(k * 2 + 1, l, r);
	return max(queryMax(k * 2, l, mid), queryMax(k * 2 + 1, mid + 1, r));
}
int main()
{
	int m;
	while(~scanf("%d%d", &n, &m)){
		memset(num, 0, sizeof(num));
		for(int i = 0; i < 5 * n + 1; ++i){
			a[i].l = a[i].r = a[i].sum = a[i].mx = a[i].lazy = 0;
		}
		for(int i = 1; i <= n; ++i){
			scanf("%d", &num[i]);
		}
		build(1, 1, n);
		char s;
		int l, r;
		for(int i = 0; i < m; ++i){
			cin >> s >> l >> r;
			if(s == 'Q'){
				printf("%d\n", queryMax(1, l, r));
			}
			else if(s == 'U'){
				change(1, l, r);
			}
		}
	}
	return 0;
}

C - A Simple Problem with Integers

要求进行区间加和区间查询。比较无脑，只是拿来练模板了，为了不瞎占篇幅这题不贴代码了

E - Just a Hook

题意&分析

数组初值全为1，要求可以进行区间改值，最后只查询数组和，也就是线段树根的权值了。这题开始线段树是自己写的了（或者说默写？总之我终于独立实现辣）

代码

#define int long long是害怕因为这个wa，实际上没有……

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
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
//int num[maxn];
int n;
struct node{
	int sum, l, r, lazy, tag;
}a[5 * maxn];
//建立线段树 
void build(int k, int l, int r){
	a[k].l = l, a[k].r = r;
	a[k].lazy = a[k].tag = a[k].sum = 0;
	if(l == r){
		a[k].sum = 1;
		return;
	}
	int mid = l + (r - l) / 2;
	build((k * 2), l, mid);
	build((k * 2) + 1, mid + 1, r);
	a[k].sum = a[2 * k].sum + a[2 * k + 1].sum;
}
void segSet(int k, int l, int r, int val){
	if(a[k].l == l && a[k].r == r)
	{
		a[k].lazy = 1;
		a[k].tag = val;
		a[k].sum = (r - l + 1) * val;
		return;
	}
	int mid = (a[k].l + a[k].r) / 2;
	
	if(a[k].lazy == 1){
		a[k].lazy = 0;
		segSet(k * 2, a[k].l, mid, a[k].tag);
		segSet(k * 2 + 1, mid + 1, a[k].r, a[k].tag);
		a[k].tag = 0;
	}
	
	if(mid >= r) segSet(2 * k, l, r, val);
	else if(mid < l) segSet(2 * k + 1, l, r, val);
	else{
		segSet(2 * k, l, mid, val);
		segSet(2 * k + 1, mid + 1, r, val);
	}
	a[k].sum = a[2 * k].sum + a[2 * k + 1].sum;
}
signed main()
{
	int t;
	scanf("%lld", &t);
	int kase = 1;
	while(t--){
//		memset(a, 0, sizeof(a));
		scanf("%lld", &n);
		build(1, 1, n);
		int m; scanf("%lld", &m);
		int xx, yy, zz;
		for(int i = 0; i < m; ++i){
			scanf("%lld%lld%lld", &xx, &yy, &zz);
			segSet(1, xx, yy, zz);
		}
		printf("Case %lld: The total value of the hook is %lld.\n", kase++, a[1].sum);
	}
	return 0;
}

F - Balanced Lineup

题意&分析

维护区间的最大值与最小值之差。由于给了5000ms时间，我就直接写了最大值查询和最小值查询，然后减掉即可。

代码

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
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int num[maxn];
int n, m;
struct node{
	int l, r, mn, mx;
}a[maxn << 2];
inline void update(int k)
{
	a[k].mn = min(a[k << 1].mn, a[(k << 1) + 1].mn);
	a[k].mx = max(a[k << 1].mx, a[(k << 1) + 1].mx);
}
//构建线段树
void build(int k, int l, int r){
	a[k].l = l, a[k].r = r;
	if(l == r){
		a[k].mx = num[l];
		a[k].mn = num[l];
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(k << 1, l, mid);
	build((k << 1) + 1, mid + 1, r);
	update(k);
}
int queryMin(int k, int l, int r)//当前线段树编号,目标左右区间 
{
	if(a[k].l == l && a[k].r == r) return a[k].mn;//找到区间
	int mid = (a[k].l + a[k].r) >> 1;
	if(r <= mid) return queryMin(k << 1, l, r);
	if(l > mid) return queryMin((k << 1) + 1, l, r);
	return min(queryMin(k << 1, l, mid), queryMin((k << 1) + 1, mid + 1, r));
}
int queryMax(int k, int l, int r)//当前线段树编号,目标左右区间 
{
	if(a[k].l == l && a[k].r == r) return a[k].mx;//找到区间
	int mid = (a[k].l + a[k].r) >> 1;
	if(r <= mid) return queryMax(k << 1, l, r);
	if(l > mid) return queryMax((k << 1) + 1, l, r);
	return max(queryMax(k << 1, l, mid), queryMax((k << 1) + 1, mid + 1, r));
}
int main()
{
	~scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) ~scanf("%d", &num[i]);
	build(1, 1, n);
	int ll, rr;
	while(m--){
		~scanf("%d%d", &ll, &rr);
		printf("%d\n", queryMax(1, ll, rr) - queryMin(1, ll, rr));
	}
	return 0;
}

G - Can you answer these queries?

题意&分析

维护一个数组，区间操作为对区间内每个数开根号。注意Lazy标记不太好传递，于是转而特判1的情况：如果区间长度等于区间和，就不再向下递归了，反正最后1开根号也不会变。

代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct node{
	int l, r;
	ll sum, lazy;//左右端点和懒惰标记 
}a[5 * maxn];
int num[maxn];
inline void update(int k){
	a[k].sum = a[k << 1].sum + a[k << 1|1].sum;
	return;
}
void build(int k, int l, int r)
{
	a[k].l = l, a[k].r = r;
	a[k].sum = a[k].lazy = 0;
	if(l == r){
		a[k].sum = num[l];
		return;
	}
	int mid = ((l + r) >> 1);
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	update(k);
}
void squareRoot(int k, int l, int r)
{
	if(a[k].sum == a[k].r - a[k].l + 1) return;
	if(a[k].l == a[k].r){
		a[k].sum = sqrt(a[k].sum * 1.0);
		return;
	}
	int mid = ((a[k].l + a[k].r) >> 1);
	if(r <= mid) squareRoot(k << 1, l, r);
	else if(l > mid) squareRoot(k << 1|1, l, r);
	else{
		squareRoot(k << 1, l, mid);
		squareRoot(k << 1|1, mid + 1, r);
	}
	update(k);
}
int query(int k, int l, int r)
{
	if(a[k].r == r && a[k].l == l) return a[k].sum;
	int mid = (a[k].l + a[k].r) >> 1;
	if(r <= mid) return query(k << 1, l, r);
	else if(l > mid) return query(k << 1|1, l, r);
	else return query(k << 1, l, mid) + query(k << 1|1, mid + 1, r);
}
signed main()
{
	int n;
	int kase = 1;
	while(~scanf("%lld", &n)){
		memset(a, 0, sizeof(a));
		memset(num, 0, sizeof(num));
		printf("Case #%d:\n", kase++);
		for(int i = 1; i <= n; ++i) scanf("%lld", &num[i]);
		build(1, 1, n);
		int m; scanf("%lld", &m);
		int x, y, z;
		while(m--){
			scanf("%lld%lld%lld", &x, &y, &z);
			if(y > z)swap(y, z);
			if(x == 0) squareRoot(1, y, z);
			else{
				printf("%lld\n", query(1, y, z));
			} 
		}
		printf("\n");
	}
	return 0;
}

I - Assign the task

题意

给一个员工数组，并给每个人指定一个上司。可以进行的操作为：1. 给某人分配任务（赋值）。赋值的时候，他的下属也会被赋予同样的值。注意下属可能还会有下属。2. 查询某人当前的任务。

分析

用线段树和并查集共同维护是可以的，不过没必要小题大做了，这题直接拿并查集来做即可。不仅代码短超多，而且运行速度也快一倍。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 50005;
int fa[maxn], task[maxn];
vector<int> ch[maxn];
void give(int x, int y)
{
	task[x] = y;
	if(!ch[x].empty()){
		for(int i = 0; i < ch[x].size(); ++i){
			give(ch[x][i], y);
		}
	}
}
int main()
{
	int t;
	scanf("%d", &t);
	int kase = 1;
	while(t--)
	{
		printf("Case #%d:\n", kase++);
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) fa[i] = i;
		for(int i = 1; i <= n; ++i) task[i] = -1;
		int u, v;
		for(int i = 1; i <= n; ++i) ch[i].clear();
		for(int i = 0; i < n - 1; ++i){
			scanf("%d%d", &u, &v);
			fa[u] = v;
			ch[v].push_back(u);
		}
		int m; scanf("%d", &m);
		char s; int x, y;
		while(m--){
			cin >> s >> x;
			if(s == 'C'){
				printf("%d\n", task[x]);
			}
			else{
				scanf("%d", &y);
				give(x, y);//把任务y分配给x. 
			}
		}
	}
	return 0;
 }