309743: CF1728G. Illumination
Memory Limit：512 MB
Time Limit：8 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Illumination
题意翻译
给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。 对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。 一次合法的照明定义为所有的点都至少被一盏灯照亮。 现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要： - 添加一盏灯在 $f_i$ 处。 - 计算有多少种合法的照明方式。 - 删除这盏灯。题目描述
Consider a segment $ [0, d] $ of the coordinate line. There are $ n $ lanterns and $ m $ points of interest in this segment. For each lantern, you can choose its power — an integer between $ 0 $ and $ d $ (inclusive). A lantern with coordinate $ x $ illuminates the point of interest with coordinate $ y $ if $ |x - y| $ is less than or equal to the power of the lantern. A way to choose the power values for all lanterns is considered valid if every point of interest is illuminated by at least one lantern. You have to process $ q $ queries. Each query is represented by one integer $ f_i $ . To answer the $ i $ -th query, you have to: - add a lantern on coordinate $ f_i $ ; - calculate the number of valid ways to assign power values to all lanterns, and print it modulo $ 998244353 $ ; - remove the lantern you just added.输入输出格式
输入格式
The first line contains three integers $ d $ , $ n $ and $ m $ ( $ 4 \le d \le 3 \cdot 10^5 $ ; $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le m \le 16 $ ) — the size of the segment, the number of lanterns and the number of points of interest, respectively. The second line contains $ n $ integers $ l_1, l_2, \dots, l_n $ ( $ 1 \le l_i \le d - 1 $ ), where $ l_i $ is the coordinate of the $ i $ -th lantern. The third line contains $ m $ integers $ p_1, p_2, \dots, p_m $ ( $ 1 \le p_i \le d - 1 $ ), where $ p_i $ is the coordinate of the $ i $ -th point of interest. The fourth line contains one integer $ q $ ( $ 1 \le q \le 5 \cdot 10^5 $ ) — the number of queries. The fifth line contains $ q $ integers $ f_1, f_2, \dots, f_q $ ( $ 1 \le f_i \le d - 1 $ ), where $ f_i $ is the integer representing the $ i $ -th query. Additional constraint on the input: during the processing of each query, no coordinate contains more than one object (i. e. there cannot be two or more lanterns with the same coordinate, two or more points of interest with the same coordinate, or a lantern and a point of interest with the same coordinate).
输出格式
For each query, print one integer — the answer to it, taken modulo $ 998244353 $ .
输入输出样例
输入样例 #1
6 1 1
4
3
3
2 1 5输出样例 #1
48
47
47输入样例 #2
6 1 2
4
2 5
2
1 3输出样例 #2
44
46输入样例 #3
20 1 2
11
15 7
1
8输出样例 #3
413输入样例 #4
20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9输出样例 #4
190431
187503
188085
189903
189708Input
题意翻译
给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。 对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。 一次合法的照明定义为所有的点都至少被一盏灯照亮。 现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要： - 添加一盏灯在 $f_i$ 处。 - 计算有多少种合法的照明方式。 - 删除这盏灯。Output
**题意翻译**
给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。
对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。
一次合法的照明定义为所有的点都至少被一盏灯照亮。
现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要：
- 在 $f_i$ 处添加一盏灯。
- 计算有多少种合法的照明方式。
- 删除这盏灯。
**题目描述**
考虑一个坐标线上的线段 $ [0, d] $。在这个线段上有 $ n $ 盏灯和 $ m $ 个兴趣点。
对于每盏灯，你可以选择它的功率——一个介于 $ 0 $ 和 $ d $（包括 $ d $ 和 $ 0 $）之间的整数。如果 $ |x - y| $ 小于或等于灯的功率，那么坐标为 $ x $ 的灯将照亮坐标为 $ y $ 的兴趣点。
如果每个兴趣点至少被一盏灯照亮，那么为所有灯选择功率值的方式被认为是有效的。
你必须处理 $ q $ 个查询。每个查询由一个整数 $ f_i $ 表示。为了回答第 $ i $ 个查询，你必须：
- 在坐标 $ f_i $ 处添加一盏灯；
- 计算所有灯的有效功率分配方式的总数，并模 $ 998244353 $ 输出；
- 删除你刚添加的那盏灯。
**输入输出格式**
**输入格式**
第一行包含三个整数 $ d $，$ n $ 和 $ m $（$ 4 \le d \le 3 \cdot 10^5 $；$ 1 \le n \le 2 \cdot 10^5 $；$ 1 \le m \le 16 $）——分别是线段的大小，灯的数量和兴趣点的数量。
第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $（$ 1 \le l_i \le d - 1 $），其中 $ l_i $ 是第 $ i $ 盏灯的坐标。
第三行包含 $ m $ 个整数 $ p_1, p_2, \dots, p_m $（$ 1 \le p_i \le d - 1 $），其中 $ p_i $ 是第 $ i $ 个兴趣点的坐标。
第四行包含一个整数 $ q $（$ 1 \le q \le 5 \cdot 10^5 $）——查询的数量。
第五行包含 $ q $ 个整数 $ f_1, f_2, \dots, f_q $（$ 1 \le f_i \le d - 1 $），其中 $ f_i $ 是表示第 $ i $ 个查询的整数。
输入的额外限制：在处理每个查询时，任何坐标上不能有超过一个对象（即不能有两个或更多的灯具有相同的坐标，两个或更多的兴趣点具有相同的坐标，或者一个灯和一个兴趣点具有相同的坐标）。
**输出格式**
对于每个查询，输出一个整数——该查询的答案，模 $ 998244353 $ 后的结果。
**输入输出样例**
**输入样例 #1**
```
6 1 1
4
3
3
2 1 5
```
**输出样例 #1**
```
48
47
47
```
**输入样例 #2**
```
6 1 2
4
2 5
2
1 3
```
**输出样例 #2**
```
44
46
```
**输入样例 #3**
```
20 1 2
11
15 7
1
8
```
**输出样例 #3**
```
413
```
**输入样例 #4**
```
20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9
```
**输出样例 #4**
```
190431
187503
188085
189903
189708
```**题意翻译** 给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。 对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。 一次合法的照明定义为所有的点都至少被一盏灯照亮。 现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要： - 在 $f_i$ 处添加一盏灯。 - 计算有多少种合法的照明方式。 - 删除这盏灯。 **题目描述** 考虑一个坐标线上的线段 $ [0, d] $。在这个线段上有 $ n $ 盏灯和 $ m $ 个兴趣点。 对于每盏灯，你可以选择它的功率——一个介于 $ 0 $ 和 $ d $（包括 $ d $ 和 $ 0 $）之间的整数。如果 $ |x - y| $ 小于或等于灯的功率，那么坐标为 $ x $ 的灯将照亮坐标为 $ y $ 的兴趣点。 如果每个兴趣点至少被一盏灯照亮，那么为所有灯选择功率值的方式被认为是有效的。 你必须处理 $ q $ 个查询。每个查询由一个整数 $ f_i $ 表示。为了回答第 $ i $ 个查询，你必须： - 在坐标 $ f_i $ 处添加一盏灯； - 计算所有灯的有效功率分配方式的总数，并模 $ 998244353 $ 输出； - 删除你刚添加的那盏灯。 **输入输出格式** **输入格式** 第一行包含三个整数 $ d $，$ n $ 和 $ m $（$ 4 \le d \le 3 \cdot 10^5 $；$ 1 \le n \le 2 \cdot 10^5 $；$ 1 \le m \le 16 $）——分别是线段的大小，灯的数量和兴趣点的数量。 第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $（$ 1 \le l_i \le d - 1 $），其中 $ l_i $ 是第 $ i $ 盏灯的坐标。 第三行包含 $ m $ 个整数 $ p_1, p_2, \dots, p_m $（$ 1 \le p_i \le d - 1 $），其中 $ p_i $ 是第 $ i $ 个兴趣点的坐标。 第四行包含一个整数 $ q $（$ 1 \le q \le 5 \cdot 10^5 $）——查询的数量。 第五行包含 $ q $ 个整数 $ f_1, f_2, \dots, f_q $（$ 1 \le f_i \le d - 1 $），其中 $ f_i $ 是表示第 $ i $ 个查询的整数。 输入的额外限制：在处理每个查询时，任何坐标上不能有超过一个对象（即不能有两个或更多的灯具有相同的坐标，两个或更多的兴趣点具有相同的坐标，或者一个灯和一个兴趣点具有相同的坐标）。 **输出格式** 对于每个查询，输出一个整数——该查询的答案，模 $ 998244353 $ 后的结果。 **输入输出样例** **输入样例 #1** ``` 6 1 1 4 3 3 2 1 5 ``` **输出样例 #1** ``` 48 47 47 ``` **输入样例 #2** ``` 6 1 2 4 2 5 2 1 3 ``` **输出样例 #2** ``` 44 46 ``` **输入样例 #3** ``` 20 1 2 11 15 7 1 8 ``` **输出样例 #3** ``` 413 ``` **输入样例 #4** ``` 20 3 5 5 7 18 1 6 3 10 19 5 4 17 15 8 9 ``` **输出样例 #4** ``` 190431 187503 188085 189903 189708 ```
给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。
对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。
一次合法的照明定义为所有的点都至少被一盏灯照亮。
现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要：
- 在 $f_i$ 处添加一盏灯。
- 计算有多少种合法的照明方式。
- 删除这盏灯。
**题目描述**
考虑一个坐标线上的线段 $ [0, d] $。在这个线段上有 $ n $ 盏灯和 $ m $ 个兴趣点。
对于每盏灯，你可以选择它的功率——一个介于 $ 0 $ 和 $ d $（包括 $ d $ 和 $ 0 $）之间的整数。如果 $ |x - y| $ 小于或等于灯的功率，那么坐标为 $ x $ 的灯将照亮坐标为 $ y $ 的兴趣点。
如果每个兴趣点至少被一盏灯照亮，那么为所有灯选择功率值的方式被认为是有效的。
你必须处理 $ q $ 个查询。每个查询由一个整数 $ f_i $ 表示。为了回答第 $ i $ 个查询，你必须：
- 在坐标 $ f_i $ 处添加一盏灯；
- 计算所有灯的有效功率分配方式的总数，并模 $ 998244353 $ 输出；
- 删除你刚添加的那盏灯。
**输入输出格式**
**输入格式**
第一行包含三个整数 $ d $，$ n $ 和 $ m $（$ 4 \le d \le 3 \cdot 10^5 $；$ 1 \le n \le 2 \cdot 10^5 $；$ 1 \le m \le 16 $）——分别是线段的大小，灯的数量和兴趣点的数量。
第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $（$ 1 \le l_i \le d - 1 $），其中 $ l_i $ 是第 $ i $ 盏灯的坐标。
第三行包含 $ m $ 个整数 $ p_1, p_2, \dots, p_m $（$ 1 \le p_i \le d - 1 $），其中 $ p_i $ 是第 $ i $ 个兴趣点的坐标。
第四行包含一个整数 $ q $（$ 1 \le q \le 5 \cdot 10^5 $）——查询的数量。
第五行包含 $ q $ 个整数 $ f_1, f_2, \dots, f_q $（$ 1 \le f_i \le d - 1 $），其中 $ f_i $ 是表示第 $ i $ 个查询的整数。
输入的额外限制：在处理每个查询时，任何坐标上不能有超过一个对象（即不能有两个或更多的灯具有相同的坐标，两个或更多的兴趣点具有相同的坐标，或者一个灯和一个兴趣点具有相同的坐标）。
**输出格式**
对于每个查询，输出一个整数——该查询的答案，模 $ 998244353 $ 后的结果。
**输入输出样例**
**输入样例 #1**
```
6 1 1
4
3
3
2 1 5
```
**输出样例 #1**
```
48
47
47
```
**输入样例 #2**
```
6 1 2
4
2 5
2
1 3
```
**输出样例 #2**
```
44
46
```
**输入样例 #3**
```
20 1 2
11
15 7
1
8
```
**输出样例 #3**
```
413
```
**输入样例 #4**
```
20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9
```
**输出样例 #4**
```
190431
187503
188085
189903
189708
```**题意翻译** 给你一个范围 $[0,d]$ 的线段。现在有 $n$ 盏灯 $m$ 个点。 对于每一盏灯，你可以选择一个 $[0,d]$ 的照明范围。一盏在 $x$ 的灯可以照亮在 $[x-d,x+d]$ 的点。 一次合法的照明定义为所有的点都至少被一盏灯照亮。 现在你有 $q$ 次询问，每次询问会给定一个整数 $f_i$，回答一次询问，你需要： - 在 $f_i$ 处添加一盏灯。 - 计算有多少种合法的照明方式。 - 删除这盏灯。 **题目描述** 考虑一个坐标线上的线段 $ [0, d] $。在这个线段上有 $ n $ 盏灯和 $ m $ 个兴趣点。 对于每盏灯，你可以选择它的功率——一个介于 $ 0 $ 和 $ d $（包括 $ d $ 和 $ 0 $）之间的整数。如果 $ |x - y| $ 小于或等于灯的功率，那么坐标为 $ x $ 的灯将照亮坐标为 $ y $ 的兴趣点。 如果每个兴趣点至少被一盏灯照亮，那么为所有灯选择功率值的方式被认为是有效的。 你必须处理 $ q $ 个查询。每个查询由一个整数 $ f_i $ 表示。为了回答第 $ i $ 个查询，你必须： - 在坐标 $ f_i $ 处添加一盏灯； - 计算所有灯的有效功率分配方式的总数，并模 $ 998244353 $ 输出； - 删除你刚添加的那盏灯。 **输入输出格式** **输入格式** 第一行包含三个整数 $ d $，$ n $ 和 $ m $（$ 4 \le d \le 3 \cdot 10^5 $；$ 1 \le n \le 2 \cdot 10^5 $；$ 1 \le m \le 16 $）——分别是线段的大小，灯的数量和兴趣点的数量。 第二行包含 $ n $ 个整数 $ l_1, l_2, \dots, l_n $（$ 1 \le l_i \le d - 1 $），其中 $ l_i $ 是第 $ i $ 盏灯的坐标。 第三行包含 $ m $ 个整数 $ p_1, p_2, \dots, p_m $（$ 1 \le p_i \le d - 1 $），其中 $ p_i $ 是第 $ i $ 个兴趣点的坐标。 第四行包含一个整数 $ q $（$ 1 \le q \le 5 \cdot 10^5 $）——查询的数量。 第五行包含 $ q $ 个整数 $ f_1, f_2, \dots, f_q $（$ 1 \le f_i \le d - 1 $），其中 $ f_i $ 是表示第 $ i $ 个查询的整数。 输入的额外限制：在处理每个查询时，任何坐标上不能有超过一个对象（即不能有两个或更多的灯具有相同的坐标，两个或更多的兴趣点具有相同的坐标，或者一个灯和一个兴趣点具有相同的坐标）。 **输出格式** 对于每个查询，输出一个整数——该查询的答案，模 $ 998244353 $ 后的结果。 **输入输出样例** **输入样例 #1** ``` 6 1 1 4 3 3 2 1 5 ``` **输出样例 #1** ``` 48 47 47 ``` **输入样例 #2** ``` 6 1 2 4 2 5 2 1 3 ``` **输出样例 #2** ``` 44 46 ``` **输入样例 #3** ``` 20 1 2 11 15 7 1 8 ``` **输出样例 #3** ``` 413 ``` **输入样例 #4** ``` 20 3 5 5 7 18 1 6 3 10 19 5 4 17 15 8 9 ``` **输出样例 #4** ``` 190431 187503 188085 189903 189708 ```