# # Codeforces Round 665 (CF1401) 题解

## # Problem A - Distance and Axis (opens new window)

### # 题解

$||\vec{AB}|-|\vec{OB}||\leq|\vec{AB}-\vec{OB}|=|\vec{OA}|=n$，因此如果$n，我们必须移动A。此时移动的最小距离为$k-n$，移动后，我们可以将B取在O点处。

#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
int n, k;
printf("%d\n", n < k ? k - n : (n + k) & 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

## # Problem B - Ternary Sequence (opens new window)

### # 题目描述

$a$$b$两个数组，它们长度相等。$a$中有$x_1$$0$$y_1$$1$$z_1$$2$$b$中有$x_2$$0$$y_2$$1$$z_2$$2$。现在要求找出一种$a$$b$的排列方式，使得$\sum_{i=1}^N f(a_i,b_i)$最大，求出这个最大值。

f(x,y)=\left\{ \begin{aligned} xy & & x>y \\ 0 & & x=y \\ -xy & & x

### # 题解

#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int x1, y1, z1, x2, y2, z2;
int zy = min(z1, y2);
int pos = 2 * zy;
z1 -= zy;
int uz = min(z1 + x1, z2);
z2 -= uz;
int neg = -2 * min(y1, z2);
printf("%d\n", pos + neg);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem C - Mere Array (opens new window)

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
int lo = *min_element(a.begin(), a.end());
vector<int> v;
for (int i = 0; i < n; ++i)
if (a[i] % lo == 0)
v.emplace_back(i);
vector<int> pos(v);
sort(v.begin(), v.end(), [&](int i, int j) { return a[i] < a[j]; });
vector<int> b(a);
for (int i = 0; i < v.size(); ++i)
b[pos[i]] = a[v[i]];
int hi = 0;
for (int i : b) {
if (i < hi) {
printf("NO\n");
return;
}
hi = i;
}
printf("YES\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem D - Maximum Distributed Tree (opens new window)

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
int n, m;
vector<int> cnt;
vector<ll> weight;
void dfs(int u, int p) {
cnt[u] = 1;
if (v != p) {
dfs(v, u);
cnt[u] += cnt[v];
}
weight[u] = (ll)cnt[u] * (n - cnt[u]);
}

public:
void solve() {
cnt = vector<int>(n + 1);
weight = vector<ll>(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
}
vector<int> p(m);
for (int i = 0; i < m; ++i)
sort(p.rbegin(), p.rend());
dfs(1, 0);
int idx = 0;
if (m > n - 1) {
for (int i = 1; m - i >= n - 1; ++i)
p[i] = (ll)p[i - 1] * p[i] % MOD;
idx = m - n + 1;
}
int ans = 0;
sort(weight.rbegin(), weight.rend());
for (int i = 0; i < n - 1; ++i)
ans = ((ll)ans + weight[i] * (i < m ? p[i + idx] : 1)) % MOD;
printf("%d\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem E - Devide Square (opens new window)

### # 题解

• $[l,r]$范围内的每条线段交点数增加$1$，也即增加了一条高度范围为$[l,r]$竖直线段，此时原本一个交点的变成两个交点，没有交点的变成一个交点
• $y$处的线段数增加$1$，此时新增一条没有交点的线段。
• $y$处的线段数减少$1$，此时所有情况都变为$0$（因为原本至多有一条）。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 1000000
#define lson (idx << 1)
#define rson (idx << 1 | 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

struct Node {
int l, r, zero = 0, first = 0, second = 0;
bool lazy = false;
} s[(MAXN + 10) << 2];

void calc(int idx) {
s[idx].zero = s[lson].zero + s[rson].zero;
s[idx].first = s[lson].first + s[rson].first;
s[idx].second = s[lson].second + s[rson].second;
}

void update(int idx) {
s[idx].second += s[idx].first;
s[idx].first = s[idx].zero;
s[idx].zero = 0;
s[idx].lazy = true;
return;
}

void pushdown(int idx) {
if (s[idx].lazy)
for (int i = lson; i <= rson; ++i)
update(i);
s[idx].lazy = false;
}

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
}

void update(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r) {
update(idx);
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson, l, r);
if (mid + 1 <= r)
update(rson, l, r);
calc(idx);
}

void inc(int idx, int pos) {
if (s[idx].l == s[idx].r && s[idx].l == pos) {
s[idx].zero++;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (pos <= mid)
inc(lson, pos);
else
inc(rson, pos);
calc(idx);
}

void dec(int idx, int pos) {
if (s[idx].l == s[idx].r && s[idx].l == pos) {
s[idx].zero = s[idx].first = s[idx].second = 0;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (pos <= mid)
dec(lson, pos);
else
dec(rson, pos);
calc(idx);
}

int query(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].second;
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
int ans = 0;
if (l <= mid)
ans += query(lson, l, r);
if (mid + 1 <= r)
ans += query(rson, l, r);
return ans;
}

class Solution {
public:
void solve() {
int n, m;
vector<pair<int, pii>> hseg, vseg;
vector<vector<int>> start(MAXN + 1), end(MAXN + 1);
for (int i = 0; i < n; ++i) {
int y, l, r;
hseg.push_back({y, {l, r}});
}
hseg.push_back({0, {0, MAXN}});
hseg.push_back({MAXN, {0, MAXN}});
for (auto p : hseg) {
int y = p.first;
int l = p.second.first, r = p.second.second;
start[l].emplace_back(y);
end[r].emplace_back(y);
}
for (int i = 0; i < m; ++i) {
int x, l, r;
vseg.push_back({x, {l, r}});
}
vseg.push_back({0, {0, MAXN}});
vseg.push_back({MAXN, {0, MAXN}});
sort(vseg.begin(), vseg.end());
ll ans = 0;
build(1, 1, MAXN + 1);
for (int i = 0; i < vseg.size(); ++i) {
auto &p = vseg[i];
int x = p.first;
for (int y : start[x])
inc(1, y + 1);
int l = p.second.first, r = p.second.second;
update(1, l + 1, r + 1);
int cross = query(1, l + 1, r + 1);
ans += max(0, cross - 1);
for (int y : end[x])
dec(1, y + 1);
if (i + 1 < vseg.size())
for (int j = x + 1; j < vseg[i + 1].first; ++j) {
for (int y : start[j])
inc(1, y + 1);
for (int y : end[j])
dec(1, y + 1);
}
}
printf("%lld", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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

## # Problem F - Reverse and Swap (opens new window)

### # 题目描述

• $replace(x,k)$，将位置$x$处的数设为$k$
• $reverse(k)$，将每一段长度为$2^k$的子区间倒序
• $swap(k)$，交换每两段相邻的长度为$2^k$的子区间
• $sum(l,r)$，求$[l,r]$范围内所有数的和

### # 题解

#include <cstdio>
#include <iostream>
#define MAXN 300005
#define lson (idx << 1)
#define rson (idx << 1 | 1)

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

int a[MAXN], ss = 0, rr = 0;
ll s[MAXN << 2];

void calc(int idx) { s[idx] = s[lson] + s[rson]; }

void build(int idx, int l, int r) {
if (l == r) {
s[idx] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
calc(idx);
}

void move(int &idx, int level) { idx = ((idx - 1) ^ (1 << (level - 1))) + 1; }

void update(int idx, int pos, int val, int level, int cl, int cr) {
if (level == 0) {
s[idx] = val;
return;
}
bool fr = (rr & (1 << level));
bool fs = (ss & (1 << level));
int mid = (cl + cr) >> 1;
if (fr)
pos = cl + cr - pos;
if (fs)
move(pos, level);
if (pos <= mid)
update(lson, pos, val, level - 1, cl, mid);
else
update(rson, pos, val, level - 1, mid + 1, cr);
calc(idx);
}

ll query(int idx, int l, int r, int level, int cl, int cr) {
if (cl >= l && cr <= r)
return s[idx];
ll ans = 0;
bool fr = (rr & (1 << level));
bool fs = (ss & (1 << level));
int mid = (cl + cr) >> 1;
if (fr)
l = cl + cr - l, r = cl + cr - r, swap(l, r);
if (r <= mid || l >= mid + 1) {
if (fs)
move(l, level), move(r, level);
if (l <= mid)
ans += query(lson, l, r, level - 1, cl, mid);
else
ans += query(rson, l, r, level - 1, mid + 1, cr);
} else {
int le = mid, rs = mid + 1;
if (fs)
move(l, level), move(le, level), move(rs, level), move(r, level);
if (l > rs)
swap(l, rs), swap(le, r);
ans += query(lson, l, le, level - 1, cl, mid);
ans += query(rson, rs, r, level - 1, mid + 1, cr);
}
return ans;
}

class Solution {
public:
void solve() {
int n, q;
int R = 1 << n;
for (int i = 1; i <= R; ++i)
build(1, 1, R);
while (q--) {
int t, x, k, l, r;
switch (t) {
case 1:
update(1, x, k, n, 1, R);
break;
case 2:
rr ^= (1 << k);
break;
case 3:
ss ^= (1 << (k + 1));
break;
default:
printf("%lld\n", query(1, l, r, n, 1, R));
}
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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