2019牛客暑期多校训练营第八场题解

本文包括2019牛客暑期多校训练营第八场的题面与题解。

A - String

题目描述

Gromah and LZR entered the great tomb, the first thing they see is a matrix of size $ n \times m $ , and the elements in the matrix are all $ 0 $ or $ 1 $ .

LZR finds a note board saying “An all-one matrix is defined as the matrix whose elements are all $ 1 $ , you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices” .

Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board!

Please help them determine the password and enter the next level.

输入描述

The first line contains two positive integers $ n,m $ denoting the size of given matrix.

Following $ n $ lines each contains a string with length $ m $ ,whose elements are allor $ 0 $ or $ 1 $ ,denoting the given matrix.

$ 1\le n,m \le 3000$

输出描述

Print a non-negative integer, denoting the answer.

示例1

输入

1
2
3
4
3 4
0111
1110
0101

输出

1
5

说明

The $5$ matrices are $ (1,2)-(1,4) $ , $ (1,2)-(2,3) $ , $ (1,2)-(3,2) $ , $ (2,1)-(2,3) $ , $ (3,4)-(3,4) $ .

题解

题意

定义完美全 $ 1 $ 矩阵为不存在包含该矩阵的全 $ 1 $ 矩阵的全 $ 1 $ 矩阵。

给定一个 $ 01 $ 矩阵,询问其中有多少完美全 $ 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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 3005
int l[N][N], r[N][N], f[N][N], n, m;
char c[N];
ll d[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
for (int j = 1; j <= m; j++)
f[i][j] = (c[j] == '1') ? f[i - 1][j] + 1 : 0;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) l[i][j] = r[i][j] = j;
f[i][0] = f[i][m + 1] = -1;
for (int j = 1; j <= m; j++)
while (f[i][j] <= f[i][l[i][j] - 1]) l[i][j] = l[i][l[i][j] - 1];
for (int j = m; j >= 1; j--)
while (f[i][j] <= f[i][r[i][j] + 1]) r[i][j] = r[i][r[i][j] + 1];
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 1; j <= m; j++)
if (f[i][j] && (i == n || f[i + 1][j] == 0 ||
(l[i][j] != l[i + 1][j] || r[i][j] != r[i + 1][j])))
d[++s] = (ll)l[i][j] << 30 | (ll)r[i][j] << 15 | (ll)f[i][j];
sort(d + 1, d + s + 1);
ans += unique(d + 1, d + s + 1) - d - 1;
}
printf("%d\n", ans);
return 0;
}

B - Beauty Values

题目描述

Gromah and LZR have entered the second level. There is a sequence $ a_1, a_2, \cdots, a_n $ on the wall.

There is also a note board saying “the beauty value of a sequence is the number of different elements in the sequence”.

LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.

Please help them determine the password!

输入描述

The first line contains one positive integer $ n $ , denoting the length of the sequence.

The second line contains $ n $ positive integers $ a_1, a_2, \cdots, a_n $ , denoting the sequence.

$ 1 \le a_i \le n \le 10^5 $

输出描述

Print a non-negative integer in a single line, denoting the answer.

示例1

输入

1
2
4
1 2 1 3

输出

1
18

说明

The beauty values of subintervals $ [1,1], [2,2], [3,3], [4,4] $ are all $ 1 $ .

The beauty values of subintervals $ [1,2], [1,3], [2,3], [3,4] $ are all $ 2 $ .

The beauty values of subintervals $ [1,4], [2,4] $ are all $ 3 $ .

As a result, the sum of all beauty values are $ 1\times 4 + 2\times 4 + 3\times 2 = 18 $ .

题解

题意

给定一个序列,对于该序列的每一个子序列,定义它的权值为该子序列包含的元素个数。

询问你该序列的全部连续子序列的权值和。

解法

如果两个元素相同,那么这两个元素在同一区间时只对答案产生一次贡献。

那么如果这 $ n $ 个元素各不相同,显然答案为 $ \dfrac{n(n+1)(n+2)}{6} $ ,如果有相同元素,那么将相同元素的影响删去即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
int last[N], n;
int main() {
scanf("%d", &n);
ll ans = (ll)n * (n + 1) * (n + 2) / 6, num = 0;
for (int i = 1, a; i <= n; ++i) {
scanf("%d", &a);
num += last[a], last[a] = i, ans -= num;
}
printf("%lld\n", ans);
return 0;
}

C - CDMA

题目描述

Gromah and LZR have entered the third level. There is a blank grid of size $ m \times m $ , and above the grid is a word “CDMA”.

In CDMA Technology, a Technology about computer network, every network node should be appointed a unique binary sequence with a fixed and the same length. Moreover, if we regard $ 0 $ in the sequence as $ -1 $ , and regard $ 1$ as $ +1$ , then these sequences should satisfy that for any two different sequences $ s,t $ , the inner product of $ s,t $ should be exactly $ 0 $ .

The inner product of two sequences $ s,t $ with the same length $ n $ equals to $ \sum_{i=1}^{n} s_it_i $ .

So, the key to the next level is to construct a grid of size $ m\times m $ , whose elements are all $ -1 $ or $ 1 $ , and for any two different rows, the inner product of them should be exactly $ 0 $ .

In this problem, it is guaranteed that $ m $ is a positive integer power of $ 2 $ and there exists some solutions for input $ m $ . If there are multiple solutions, you may print any of them.

输入描述

Only one positive integer $ m $ in one line.

$ m \in \{2^k \; | \;k = 1, 2, \cdots, 10\} $

输出描述

Print $ m $ lines, each contains a sequence with length $ m $ , whose elements should be all $ -1 $ or $ 1 $ satisfying that for any two different rows, the inner product of them equals $ 0 $ .

You may print multiple blank spaces between two numbers or at the end of each line, and you may print any number of blank characters at the end of whole output file.

示例1

输入

1
2

输出

1
2
1 1
1 -1

说明

The inner product of the two rows is $ 1\times(-1) + 1\times 1 = 0 $ .

题解

题意

构造一个由 $ 1 $ 和 $ -1 $ 组成的 $ m \times m $ ( $ m = 2^k $ ) 的矩阵,要求对于任意两个不同的行的内积为 $ 0 $ 。

解法

假定 $ m = 2^k $ 时的一个解为矩阵 $ A $ ,那么 $ m = 2^{k+1} $ 时的解为 $ \begin{bmatrix} A & A \\ A & -A \end{bmatrix} $ .

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
int mp[1024][1024] = {1}, m;
int main() {
scanf("%d", &m);
for (int c = 1; c < m; c <<= 1)
for (int i = 0; i < c; ++i)
for (int j = 0; j < c; ++j)
mp[i + c][j + c] = -(mp[i + c][j] = mp[i][j + c] = mp[i][j]);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) printf("%d ", mp[i][j]);
putchar('\n');
}
return 0;
}

D - Distance

题目描述

Gromah and LZR have entered the fourth level. There is a blank cube with size $ n\times m\times h $ hanging on the wall.

Gromah soon finds a list beside the cube, there are $ q $ instructions in the list and each instruction is in one of the following two formats:

  1. $ (1, x, y, z) $ , meaning to add a tag on position $ (x, y, z) $ in the cube
  2. $ (2,x, y, z) $ , meaning to determine the minimum Manhattan Distance to the given position $ (x, y, z) $ among all tagged positions

Manhattan Distance between two positions $ (x_1, y_1, z_1), (x_2, y_2, z_2) $ is defined as $ |x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2| $ .

LZR also finds a note board saying that the password of this level is the sequence made up of all results of the instructions in format $ 2 $ .

Please help them get all results of the instructions in format $ 2 $ .

输入描述

The first line contains four positive integers $ n,m,h,q $ , denoting the sizes in three dimensions of the cube and the number of instructions.

Following $ q $ lines each contains four positive integers $ op,x, y, z $ , where $ op=1 $ means to add a tag on $ (x,y,z) $ while $ op=2 $ means to make a query on $ (x,y,z) $ .

$ 1 \le n\times m\times h, q\le 10^5, 1 \le x \le n, 1 \le y \le m, 1 \le z \le h $

It is guaranteed that the first instruction is in format $ 1 $ and that no position will be tagged more than once.

输出描述

For each instruction in format $ 2 $ , output the answer in one line.

示例1

输入

1
2
3
4
5
3 3 3 4
1 1 1 1
2 2 3 3
1 3 1 1
2 3 3 2

输出

1
2
5
3

说明

For the first query, there is only one tagged position $ (1,1,1) $ currently, so the answer is $ |1-2| + |1-3| + |1-3| = 5 $ .

For the second query, $ (3,1,1) $ is the nearest tagged position, so the answer is $ |3-3| + |1-3| + |1-2| = 3 $ .

题解

题意

三维空间中,两种操作,一是标记一个点,二是询问一个点,每次询问要求输出询问点与标记点的最小曼哈顿距离。

解法

已知两点 $ (x,y,z) $ 与 $ (x’,y’,z’) $ 距离为 $ |x-x’|+|y-y’|+|z-z’| $ .

那么根据绝对值符号内的正负,分八种情况讨论即可,使用树状数组维护。

代码

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 <bits/stdc++.h>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
int n, m, h, Q;
struct {
int d[N];
void init() { memset(d, 128, sizeof d); }
int lowbit(int x) { return x & (-x); }
int f(int i, int j, int k) { return (i - 1) * m * h + (j - 1) * h + k; }
void getmax(int &a, int b) {
if (b > a) a = b;
}
void updata(int x, int y, int z, int w) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j))
for (int k = z; k <= h; k += lowbit(k))
getmax(d[f(i, j, k)], w);
}
int sum(int x, int y, int z) {
int res = -INF;
for (int i = x; i > 0; i -= lowbit(i))
for (int j = y; j > 0; j -= lowbit(j))
for (int k = z; k > 0; k -= lowbit(k))
getmax(res, d[f(i, j, k)]);
return res;
}
} t[8];
int main() {
for (int i = 0; i < 8; i++) t[i].init();
scanf("%d%d%d%d", &n, &m, &h, &Q);
while (Q--) {
int kind, x, y, z;
scanf("%d%d%d%d", &kind, &x, &y, &z);
if (kind == 1) {
t[0].updata(x, y, z, x + y + z);
t[1].updata(x, y, h - z + 1, x + y - z);
t[2].updata(x, m - y + 1, z, x - y + z);
t[3].updata(x, m - y + 1, h - z + 1, x - y - z);
t[4].updata(n - x + 1, y, z, -x + y + z);
t[5].updata(n - x + 1, y, h - z + 1, -x + y - z);
t[6].updata(n - x + 1, m - y + 1, z, -x - y + z);
t[7].updata(n - x + 1, m - y + 1, h - z + 1, -x - y - z);
} else {
int ans = INF;
ans = min(ans, x + y + z - t[0].sum(x, y, z));
ans = min(ans, x + y - z - t[1].sum(x, y, h - z + 1));
ans = min(ans, x - y + z - t[2].sum(x, m - y + 1, z));
ans = min(ans, x - y - z - t[3].sum(x, m - y + 1, h - z + 1));
ans = min(ans, -x + y + z - t[4].sum(n - x + 1, y, z));
ans = min(ans, -x + y - z - t[5].sum(n - x + 1, y, h - z + 1));
ans = min(ans, -x - y + z - t[6].sum(n - x + 1, m - y + 1, z));
ans = min(ans, -x - y - z - t[7].sum(n - x + 1, m - y + 1, h - z + 1));
printf("%d\n", ans);
}
}
return 0;
}

E - Explorer

题目描述

Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.

There are $ n $ vertices and $ m $ bidirectional roads in this level, each road is in format $ (u, v, l, r) $ ,which means that vertex $ u $ and $ v $ are connected by this road, but the sizes of passers should be in interval $ [l,r] $ . Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.

Moreover, vertex $ 1 $ is the starting point and vertex $ n $ is the destination. Gromah and LZR should go from vertex $ 1 $ to vertex $ n $ to enter the next level.

At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from $ 1 $ to $ n $ .

Please help them to find the number of valid sizes.

输入描述

The first line contains two positive integers $ n,m $ , denoting the number of vertices and roads.

Following m lines each contains four positive integers $ u, v, l, r $ , denoting a bidirectional road $ (u, v, l, r) $ .

$ 1 \le n,m \le 10^5, 1 \le u < v \le n, 1 \le l \le r \le 10^9 $

输出描述

Print a non-negative integer in a single line, denoting the number of valid sizes.

示例1

输入

1
2
3
4
5
6
5 5
1 2 1 4
2 3 1 2
3 5 2 4
2 4 1 3
4 5 3 4

输出

1
2

说明

There are $ 2 $ valid sizes : $ 2 $ and $ 3 $ .

For size $ 2 $ , there exists a path $ 1 \rightarrow 2 \rightarrow 3 \rightarrow 5 $ .

For size $ 3 $ , there exists a path $ 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 $ .

题解

题意

给定一张有向图,图上每一条边允许通过 $ [l,r] $ 范围的数字。

询问从 $ 1 $ 号点到 $ n $ 号点能有多少种数字经过。

解法

用线段树模拟并查集维护连通性。

代码

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;
#define ll long long
#define N 100010
vector<int> e[N << 3];
int n, m, size[N], a[N << 1], ans, cnt;
int l[N], r[N], u[N], v[N], f[N];
inline int fa(int x) { return x == f[x] ? f[x] : fa(f[x]); }
void ins(int k, int nl, int nr, int l, int r, int x) {
if (nl == l && nr == r) {
e[k].push_back(x);
return;
}
int mid = (nl + nr) >> 1;
if (r <= mid)
ins(k << 1, nl, mid, l, r, x);
else if (l > mid)
ins(k << 1 | 1, mid + 1, nr, l, r, x);
else {
ins(k << 1, nl, mid, l, mid, x);
ins(k << 1 | 1, mid + 1, nr, mid + 1, r, x);
}
}
void dfs(int k, int l, int r) {
vector<int> lastf;
int m = e[k].size(), mid = (l + r) >> 1;
for (register int i = 0; i < m; i++) {
int x = fa(u[e[k][i]]), y = fa(v[e[k][i]]);
if (size[x] > size[y]) swap(x, y);
lastf.push_back(x);
f[x] = y, size[y] += size[x];
}
if (fa(1) == fa(n))
ans += a[r + 1] - a[l];
else if (l < r)
dfs(k << 1, l, mid), dfs(k << 1 | 1, mid + 1, r);
m = lastf.size();
for (int i = m - 1; i >= 0; i--) f[lastf[i]] = lastf[i];
lastf.clear();
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) f[i] = i, size[i] = 1;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &u[i], &v[i], &l[i], &r[i]);
a[++cnt] = l[i], a[++cnt] = r[i] + 1;
}
sort(a + 1, a + 1 + cnt);
cnt = unique(a + 1, a + 1 + cnt) - a - 1;
for (int i = 1; i <= m; i++)
ins(1, 1, cnt - 1, lower_bound(a + 1, a + 1 + cnt, l[i]) - a,
lower_bound(a + 1, a + 1 + cnt, r[i] + 1) - a - 1, i);
dfs(1, 1, cnt - 1);
printf("%d\n", ans);
return 0;
}

F - Flower Dance

题目描述

Gromah and LZR have entered the sixth level.

There are $ n $ pairwise distinct points on the wall, each can be described as $ P_i(x_i, y_i) \;(1\le i\le n) $ in a 2-dimensional rectangular coordinate system.

LZR finds a note board saying that four distinct points $ A,B,C,D $ form a flower if there exists a point among the four points strictly inside the triangle formed by the other three points, where the triangle should be non-degenerate.

So the password of this level is naturally the number of tuples $ (i,j,k,l)(1 \le i < j < k < l \le n) $ that $ P_i, P_j, P_k, P_l $ form a flower.

Please help them to calculate the answer.

输入描述

The first line contains one positive integer $ n $ , denoting the number of points.

Following $ n $ lines each contains two integers $ x_i, y_i $ , denoting a point.

$ 4 \le n \le 1000, |x|,|y| \le 10^9 $

$ n $ points are pairwise distinct.

输出描述

Print a non-negative integer in a single line, denoting the number of flowers.

示例1

输入

1
2
3
4
5
6
7
8
9
8
0 0
0 1
-1 0
0 -1
1 1
1 -1
-1 1
-1 -1

输出

1
5

说明

The 5 flowers are

G - Gemstones

题目描述

Gromah and LZR have entered the seventh level. There are a sequence of gemstones on the wall.

After some tries, Gromah discovers that one can take exactly three successive gemstones with the same types away from the gemstone sequence each time, after taking away three gemstones, the left two parts of origin sequence will be merged to one sequence in origin order automatically.

For example, as for “ATCCCTTG”, we can take three ‘C’s away with two parts “AT”, “TTG” left, then the two parts will be merged to “ATTTG”, and we can take three ‘T’s next time.

The password of this level is the maximum possible times to take gemstones from origin sequence.

Please help them to determine the maximum times.

输入描述

Only one line containing a string $ s $ , denoting the gemstone sequence, where the same letters are regarded as the same types.

$ 1 \le |s| \le 10^5 $

$ s $ only contains uppercase letters.

输出描述

Print a non-negative integer in a single line, denoting the maximum times.

示例1

输入

1
ATCCCTTG

输出

1
2

说明

One possible way is that $ ATCCCTTG \rightarrow ATTTG \rightarrow AG $ .

题解

题意

给定一段字符串,串中连续的三个相同字符可以消去,消去后剩下的字符串拼接,求最多可消去次数。

解法

用栈模拟。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int ans, sta[N], top;
char s[N];
int main() {
scanf("%s", s);
for (int i = 0; s[i]; i++) {
sta[++top] = s[i];
if (top >= 3 && sta[top] == sta[top - 1] && sta[top] == sta[top - 2])
top -= 3, ans++;
}
printf("%d\n", ans);
return 0;
}

H - How Many Schemes

题目描述

Gromah and LZR have entered the eighth level. There is an $ n $ -vertex tree, acyclic bidirectional connected graph painted on the wall. The vertices are conveniently labeled with $ 1, 2, \cdots, n $ .

LZR finds that for every edge $ e $ in the tree, there is a non-empty set of lowercase letters ses_ese above it. Meanwhile, Gromah finds $ m $ strings $ t_1, t_2, \cdots, t_m $ and $ q $ queries $ (u_1, v_1), (u_2, v_2), \cdots, (u_q, v_q) $ beside the tree.

Soon, LZR finds a note board saying that for each query $ (u,v) $ , you may choose exactly one letter from ses_ese for all edges $ e $ in the chain $ u \rightarrow v $ and write down the chosen letters in the order of the directed chain $ u\rightarrow v $ to form a string $ str $ , and the answer to this query is the number of schemes to choose letters so that the result string $ str $ completely contains at least one of the $ m $ given strings $ t_1, t_2, \cdots, t_m $ .

Moreover, the answers to queries may be very large, so they only need to know the answers modulo $ 998244353 $ .

Please help them answer the queries to enter the next level.

输入描述

The first line contains three positive integers $ n,m,q $ , denoting the size of the tree, the number of given strings and the number of queries.

Following $ n-1 $ lines each contains two positive integers $ u,v $ and a string $ str_e $ , denoting an edge between $ u $ and $ v $ with a set $ \{c \; | \; c \in str_e\} $ above it.

Following $ m $ lines each contains a string $ t_i $ .

Following $ q $ lines each contains two positive integers $ u,v $ , denoting a query $ (u,v) $ .

$ 1\le n\le 2500, 1\le q\le 5000, 1\le m, \sum|t_i| \le 40 $

The given graph forms a tree.

$ str_e $ only contains pairwise distinct lowercase letters.

$ t_i $ only contains lowercase letters.

$ u \neq v $ for all queries.

输出描述

Output $ q $ lines, each contains one non-negative integer denoting the answer to corresponding query modulo $ 998244353 $ .

示例1

输入

1
2
3
4
5
6
7
8
9
10
5 2 3
1 2 nkei
1 3 ieu
2 4 nk
2 5 ne
niu
ke
3 4
4 3
3 5

输出

1
2
3
0
6
3

说明

For the first query, there is no valid scheme.

For the second query, the 6 result strings are $ niu, nke, kke, kei, kee, keu $ .

For the third query, the 3 result strings are $ ike, eke, uke $ .

I - Inner World

题目描述

Gromah and LZR are transfered to a forest, maybe it is the inner world of the great tomb. Initially, there are $ n $ rooted trees numbered from $ 1 $ to $ n $ with size $ 1 $ in the forest. For each tree, the only node is the root and labeled with $ 1 $ .

After a while, here comes a farmer, and the farmer gives them $ m $ planting tasks, each can be described by a tuple $ (u,v,l,r) $ , which means to add a labeled node $ v $ for all trees numbered from $ l $ to $ r $ , and their parent nodes are the nodes labeled with $ u $ for each tree.

After finishing the planting tasks one by one, the farmer will give them $ q $ querying tasks, each can be described by a tuple $ (x,l,r) $ , which means to query the sum of sizes of subtrees whose roots are the nodes labeled with $ x $ among the trees numbered from $ l $ to $ r $ . Specially, if there isn’t a node labeled with $ x $ in a tree, the size of subtree $ x $ is regarded as $ 0 $ .

If they complete all tasks perfectly, the farmer will help them pass the final level.

Please help them handle these tasks.

输入描述

The first line contains two positive integers $ n,m $ , denoting the number of trees in the inner world and the number of planting tasks.

Following $ m $ lines each contains four positive integers $ u,v,l,r $ , denoting a planting task $ (u,v,l,r) $ .

The next line contains one positive integer $ q $ , denoting the number of querying tasks.

Following $ q $ lines each contains four positive integers $ x,l,r $ , denoting a querying task $ (x,l,r) $ .

$ 1\le n,m,q \le 300000 $ , $ 1 \le u,x \le m + 1 $ , $ 2 \le v \le m + 1 $ , $ 1 \le l \le r \le n $

For each planting task, It is guaranteed that the label vv_{}v is unique among all vv_{}vs, and the trees numbered from $ l $ to $ r $ all have a node labeled with $ u $ right before handling this task.

输出描述

Output $ q $ lines, each contains one non-negative integer denoting the answer to corresponding query task.

示例1

输入

1
2
3
4
5
6
7
4 3
1 2 1 2
1 3 2 4
3 4 2 3
2
1 1 4
3 1 4

输出

1
2
11
5

说明

Four trees are 1-2, 1(-2)-3-4, 1-3-4, 1-3.

In the four trees, sizes of subtrees 1 are 2,4,3,2, so the answer to the first query task is 2+4+3+2=11, while the sizes of subtrees 3 are 0,2,2,1 and the answer to the second query task is 0+2+2+1=5.

题解

题意

给定 $ n $ 棵树,每棵树初始只有一个节点 $ 1 $ 。接下来给定 $ m $ 次操作,每次操作给定一个区间 $ [l,r] $ 和一对结点 $ (u,v) $ ,表示将该区间内的树上的节点 $ u $ 都和 $ v $ 连一条边,保证每一个 $ v $ 只出现一次。最后给定 $ q $ 次询问,每次询问给定一个点 $ x $ 和一个区间 $ [l,r] $ ,询问你该区间中所有以 $ x $ 节点为根节点的子树大小之和。

解法

每个节点作为子节点被添加到树上最多一次,那么按照 $ dfs $ 序排序后以 $ x $ 节点为根节点的子树的节点的 $ dfs $ 序必定是连续的。

考虑主席树,我们以 $ dfs $ 序为主席树的版本,每个节点就让 $ (ql,qr) $ 之间的树加一,最后只需要将 $ ou[x] $ 和 $ in[x]-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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
int n, m, q, tot, ti;
int root[N], l[N], r[N], in[N], ou[N], re[N];
struct node {
int l, r;
ll sum, lazy;
} tr[N * 65];
vector<int> ve[N];
void dfs(int u) {
in[u] = ++ti, re[ti] = u;
for (auto it : ve[u]) dfs(it);
ou[u] = ti;
}
void update(int &rt, int pre, int l, int r, int ql, int qr, ll val) {
tr[rt = ++tot] = tr[pre], tr[rt].sum += (qr - ql + 1) * val;
if (ql <= l && r <= qr) {
tr[rt].lazy += val;
return;
}
int s = (l + r) >> 1;
if (ql <= s) update(tr[rt].l, tr[pre].l, l, s, ql, min(qr, s), val);
if (s < qr) update(tr[rt].r, tr[pre].r, s + 1, r, max(s + 1, ql), qr, val);
}
ll query(int rt, int pre, int l, int r, int ql, int qr, ll add) {
if (ql <= l && r <= qr) return tr[rt].sum - tr[pre].sum + (r - l + 1) * add;
add += tr[rt].lazy - tr[pre].lazy;
int s = (l + r) >> 1;
ll res = 0;
if (ql <= s) res += query(tr[rt].l, tr[pre].l, l, s, ql, qr, add);
if (s < qr) res += query(tr[rt].r, tr[pre].r, s + 1, r, ql, qr, add);
return res;
}
int main() {
scanf("%d%d", &n, &m);
l[1] = 1, r[1] = n;
for (int i = 1, u, v, x, y; i <= m; i++) {
scanf("%d%d%d%d", &u, &v, &x, &y);
ve[u].push_back(v);
l[v] = x, r[v] = y;
}
dfs(1);
for (int i = 1; i <= ti; i++)
update(root[i], root[i - 1], 1, n, l[re[i]], r[re[i]], 1);
scanf("%d", &q);
int x, l, r;
while (q--) {
scanf("%d%d%d", &x, &l, &r);
printf("%lld\n", query(root[ou[x]], root[in[x] - 1], 1, n, l, r, 0));
}
return 0;
}

J - Just Jump

题目描述

Gromah and LZR have entered the final level. In this level, they need to cross the sea of death to gain the treasures.

The sea of death is of width $ L $ , and there are $ L-1 $ stones inside the sea. Assume that Gromah and LZR are at position $ 0 $ initially, that the treasures are at position $ L $ , and that stones are at position $ 1,2, \cdots, L-1 $ respectively. So Gromah and LZR can jump on the stones to cross the sea.

Unfortunately, the stones are not stable. To ensure safety, Gromah and LZR should go forward at least $ d $ ositions not less than $ x+d $ . Moreover, they can’t be at positions greater than $ L $ in any time, which means that the destination of their last jump should be exactly position $ L $ , or the treasure keepers will see them and come to eat them.

More unfortunately, the Infernos under the sea will attack them $ m $ times in total, each attack can be described as a tuple $ (t,p) $ , denoting that the stone at position $ p $ will be attacked right after their $ t $ -th jump, which means their destination of $ t $ -th jump can’t be position $ p $

But fortunately, here comes the farmer(mentioned in problem I but not necessary to care in this problem) and he tells Gromah and LZR all the attack plans, so they can work out some jumping plans according to the information given by the farmer to get to the destination without being attacked.

Please help them determine the number of jumping plans satisfying all the restrictions described above. Since the number may be very large, you should report it modulo $ 998244353 $ .

Two jumping plans are considered different if there exists at least one $ t $ that their positions after $ t $ -th jump are different in two plans.

输入描述

The first line contains three positive integers $ L,d,m $ , denoting the width of the sea, the lower bound of jumping distance, and the number of attacks.

Following $ m $ lines each contains two positive integers $ t,p $ denoting an attack $ (t,p) $ .

$ 1 \le d \le L \le 10^7, 1 \le t,p < L, 1 \le m \le 3000 $

$ m $ attacks are pairwise distinct, where two attacks $ (t_1, p_1), (t_2, p_2) $ are considered different if $ t_1 \neq t_2 $ or $ p_1 \neq p_2 $ or both.

输出描述

Print a non-negative integer in one line, denoting the answer modulo $ 998244353 $ .

示例1

输入

1
2
5 2 1
1 2

输出

1
2

说明

There are three plans originally : $ 0\rightarrow 2 \rightarrow 5, \; 0\rightarrow 3 \rightarrow 5, \; 0\rightarrow 5 $ . But after the first jump, the stone at position 2 will be attacked, so plan $ 0 \rightarrow 2 \rightarrow 5 $ should be abandoned and 2 valid plans remain.

题解

题意

给定从 $ 0 $ 到 $ L $ 的一个区间,现在你在位置 $ 0 $ ,每次你必须跨越不少于 $ d $ 的距离,同时给定 $ q $ 组限制 $ (t_i,p_i) $ ,表示你在第 $ t_i $ 步跨越时不能落在位置 $ p_i $ 。询问你最终落在 $ L $ 上的方案数。

解法

设 $ F(i,j) $ 为走 $ i $ 次前进 $ j $ 步的方案数,相当于 $ j-i \times d $ 个相同的球装进 $ i $ 个不相同的盒子: $ C_{j-d \times i+i-1}^{j-d \times i}
$

设 $ InfF(j) $ 为走任意次前进 $ j $ 步的方案数,这个直接用前缀和转移:

考虑不合法的方案数。为了排除重复,我们枚举以每一个限制作为第一个不合法的情况。

对于限制 $ (t_i,p_i) $ ,记录到达第 $ t_i $ 步恰好到达 $ p_i $ ,之前其他限制合法的方案数 $ dp[i] $ 。

考虑 $ p_j<p_i $ , $ dp[j] $ 考虑的情况为 $ j $ 不合法, $ k<j $ , $ k $ 合法。而 $ dp[k] $ 考虑的是 $ k $ 不合法。

分析后可知 $ dp[j] $ 和 $ dp[k] $ 没有交集,所以有:

最后的答案为:

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353ll
#define N 3005
#define M 10000007
ll Qpow(ll a, ll b) {
if (b < 0) return 0;
ll ans = 1ll;
while (b) {
if (b % 2) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
ll inv(ll a) { return Qpow(a, mod - 2); }
ll fac[M];
ll inv_fac[M];
void init_fac() {
fac[0] = fac[1] = 1ll;
for (int i = 2; i < M; i++) fac[i] = fac[i - 1] * i % mod;
inv_fac[M - 1] = Qpow(fac[M - 1], mod - 2);
for (ll i = M - 2; i >= 1; i--)
inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % mod;
inv_fac[0] = 1;
}

struct node {
ll t, p;
bool operator<(const node& a) const { return p < a.p; }
} Q[N];
ll L, d, m;
ll C(int n, int m) {
if (n < 0 || m > n) return 0;
return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}
ll F(ll t, ll p) {
if (t == 0) return p == 0;
if (t < 0 || p < d * t) return 0;
return C(p - d * t + t - 1, p - d * t);
}
ll dp[N];
ll InfF[M];
int main() {
init_fac();
scanf("%lld%lld%lld", &L, &d, &m);
for (int i = 1; i <= m; i++) scanf("%lld%lld", &Q[i].t, &Q[i].p);
InfF[0] = 1;
for (int i = 1; i < d; i++) InfF[i] = 1;
for (int i = d; i <= L; i++) {
InfF[i] = InfF[i - d];
InfF[i] = (InfF[i] + InfF[i - 1]) % mod;
}
sort(Q + 1, Q + 1 + m);
for (int i = 1; i <= m; i++) {
dp[i] = F(Q[i].t, Q[i].p);
if (dp[i] == 0) continue;
for (int j = 1; j < i; j++) {
if (Q[j].t >= Q[i].t) continue;
if (Q[i].p - Q[j].p < (Q[i].t - Q[j].t) * d) continue;
dp[i] -= dp[j] * F(Q[i].t - Q[j].t, Q[i].p - Q[j].p) % mod;
}
dp[i] = (dp[i] % mod + mod) % mod;
}
ll ans = InfF[L] - InfF[L - 1];
for (int i = 1; i <= m; i++) {
if (L - Q[i].p < 0) continue;
ll s = L - Q[i].p == 0 ? 0 : InfF[L - Q[i].p - 1];
ans -= dp[i] * (InfF[L - Q[i].p] - s);
ans %= mod;
}
printf("%lld\n", (ans + mod) % mod);
return 0;
}