比赛时间:

比赛概览

比赛信息
• 比赛链接：AtCoder Beginner Contest 417
• 时间：2025-08-02(Sat) 20:00 - 2025-08-02(Sat) 21:40 (当地时间) (100 minutes)
• 排名：3510
• 解题数：3/7
• Rating变化：+99 (458 → 557)



A. A Substring

题目链接：Problem A - A Substring
时间限制：2秒/测试用例
内存限制：1024MB

题目描述

给定一个长度为 $N$ 的字符串 $S$，请从中移除前 $A$ 个字符和后 $B$ 个字符，并输出剩下的子字符串。

输入格式

输入包含四行：

  • 第一行包含一个整数 $N$ —— 字符串的长度 ($1 \leq N \leq 20$)
  • 第二行包含一个整数 $A$ —— 需要移除的前缀字符数 ($0 \leq A$)
  • 第三行包含一个整数 $B$ —— 需要移除的后缀字符数 ($0 \leq B$)
  • 第四行是一个长度为 $N$ 的字符串 $S$，仅由小写英文字母组成
  • 保证 $A + B < 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
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
/*

*/
void slu() {
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    string t;
    for (int i = a; i < n - b; i++) {
        t += s[i];
    }
    cout << t << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}



B. Search and Delete

题目链接：Problem B - Search and Delete
时间限制：2秒/测试用例
内存限制：1024MB

题目描述

Takahashi 有一个长度为 $N$ 的非递减整数序列 $A = (A_1, A_2, \dots, A_N)$。他会对该序列执行 $M$ 次操作，第 $i$ 次操作是：

  • 如果 $A$ 中存在一个值等于 $B_i$ 的元素，就从中删除一个这样的元素；如果不存在则什么也不做。

注意，因为 $A$ 是非递减序列，每次删除哪个满足条件的元素不会影响结果，最终序列仍然是非递减的。

请你输出所有操作结束后，序列 $A$ 的最终状态。

输入格式

输入由多行组成：

  • 第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq 100$）
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 10^9$），非递减排列
  • 第三行包含 $M$ 个整数 $B_1, B_2, \dots, B_M$（$1 \leq B_i \leq 10^9$）

解题思路

喵喵 详细分析

模拟：

  • 对数组变化情况模拟即可

代码实现

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
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
/*

*/
void slu() {
    map<int, int> mp;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        mp[t]++;
    }
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        mp[t]--;
    }
    for (auto [x, y] : mp) {
        while (y > 0) {
            cout << x << " ";
            y--;
        }
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}



C. Distance Indicators

题目链接：Problem C - Distance Indicators
时间限制：2秒/测试用例
内存限制：1024MB

题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。

请你计算有多少对整数 $(i, j)$ 满足以下两个条件：

  • $1 \leq i < j \leq N$
  • $j - i = A_i + A_j$

输入格式

输入包含两行：

  • 第一行是一个整数 $N$（$1 \leq N \leq 2 \times 10^5$）
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 2 \times 10^5$）

解题思路

喵喵 详细分析

公式转变：

  • 由 $j - i = A_i + A_j$ $\Longleftrightarrow$ $j - A_j = i + A_i$

新的性质：

  • 由于 $i < j$，所以我们从右（$n - 1$ 位置）开始往左遍历，把遍历过的点在左侧的权值( $j - A_j$) 存入 map 中。
  • 每次遇到新的点，用等式的右侧权值 ( $i + A_i$) 来判断是否存在相同的左侧权值( $j - A_j$)。

代码实现

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
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
/*

*/
void slu() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        int u = a[i] + i;
        cnt += mp[u];
        mp[i - a[i]]++;
    }
    cout << cnt << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}



D. Takahashi’s Expectation

题目链接：Problem D - Takahashi’s Expectation
时间限制：2秒/测试用例
内存限制：1024MB

题目描述

高桥将会收到 $N$ 个礼物。

他有一个叫做「心情」的参数，是一个非负整数。每次收到礼物时，这个心情值会发生变化。
每个礼物有三个参数：价值 $P$、心情上升量 $A$、心情下降量 $B$，规则如下：

  • 如果当前收到的礼物价值 $P$ 满足 $P \geq$ 当前心情值，他会开心，心情值增加 $A$。
  • 如果 $P <$ 当前心情值，他会失望，心情值减少 $B$，但如果当前心情小于 $B$，则变为 $0$。

第 $i$ 个礼物对应的三个参数是 $P_i, A_i, B_i$。

现在给出 $Q$ 个询问，每个询问提供一个初始心情值 $X_i$，你需要输出收完所有 $N$ 个礼物后最终的心情值。

输入格式

输入包含多行：

  • 第一行包含一个整数 $N$（$1 \leq N \leq 10^4$）
  • 接下来 $N$ 行每行三个整数 $P_i, A_i, B_i$（$1 \leq P_i, A_i, B_i \leq 500$）
  • 接下来一行包含一个整数 $Q$（$1 \leq Q \leq 5 \times 10^5$）
  • 接下来 $Q$ 行每行一个整数 $X_i$（$0 \leq X_i \leq 10^9$）

解题思路

喵喵 详细分析

思考使用方法：

  • 由于题目只要求你输出最终答案，不关心中间过程的具体路径，所以我们考虑使用动态规划（DP）来优化解法。

状态转移方程：

  • 我们设 $dp_{i,j}$ 表示当前心情值为 $j$ 时，收到第 $i$ 个礼物之后，处理完从第 $i$ 到第 $N$ 个礼物后的最终心情值。
  • 状态转移规则如下：
    • 如果 $j \leq P_i$，那么当前是开心的：
      $$ dp[i][j] = dp[i+1][j + A_i] $$
    • 如果 $j > P_i$，那么当前是失望的：
      $$ dp[i][j] = dp[i+1][\max(0, j - B_i)] $$
  • 为什么这么设定转移呢？因为我们选择从最后一个礼物往前倒推，这样当收到最后一个礼物时心情就是最终结果，我们从已知状态回溯推导。如果从前往后正推，就需要记录更多路径，效率更低。

参数边界：

  • 对于 $i$：我们需要 $N$ 层来覆盖所有 $N$ 个礼物。
  • 对于 $j$：心情值理论上会在 $[0, 1000]$ 范围内变动，因为最大为 $500 + 500$，所以我们设置最大心情值上限为 $1000$ 即可，避免内存爆炸。
  • 故最终构建一个 $dp[N+1][1001]$ 的二维数组。

特殊情况处理：

  • 当初始心情值 $X$ 很大（例如 $> 10^9$）时，我们不能直接用它作为 $dp$ 下标。
  • 但可以观察到，过大的 $X$ 会因连续失望而不断减小。我们预处理 $B$ 的前缀和并用二分查找判断：
    • 找到一个前缀区间，使得 $X$ 连续扣除这些 $B_i$ 后小于 $1000$，即可跳入我们预处理的 $dp$ 数组中求解。

代码实现

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
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
/*

*/
void slu() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), p(n), pre(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> a[i] >> b[i];
        pre[i + 1] += pre[i] + b[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(1001, 0));

    for (int i = 0; i <= 1000; i++) dp[n][i] = i;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= 1000; j++) {
            if (j <= p[i]) {
                dp[i][j] = dp[i + 1][j + a[i]];
            } else {
                dp[i][j] = dp[i + 1][max(j - b[i], O)];
            }
        }
    }
    // cout << "pre: ";
    // for (int i = 0; i < 6; i++) cout << dp[0][i] << " ";
    // cout << endl;
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        auto it =
            upper_bound(pre.begin(), pre.end(), max(O, x - 500)) - pre.begin();
        if (it == n + 1) {
            cout << x - pre.back() << endl;
        } else {
            // cout << "x: " << x << ' ' << it << endl;
            it--;
            x -= pre[it];
            cout << dp[it][x] << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}



E. A Path in A Dictionary

题目链接：Problem E - A Path in A Dictionary
时间限制：2秒/测试用例
内存限制：1024MB

题目描述

给定一个简单连通无向图 $G$，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1, 2, \dots, N$。
第 $i$ 条边 $(1 \leq i \leq M)$ 连接顶点 $U_i$ 和 $V_i$。

请找出从顶点 $X$ 到顶点 $Y$ 的字典序最小的简单路径。
简单路径要求顶点不重复。
字典序比较规则为：对于两个序列 $P$ 和 $Q$，找到最小的不同位置 $k$，若 $P_k < Q_k$，则 $P$ 字典序更小。

路径 $P = (P_1, P_2, \dots, P_{|P|})$ 需满足：

  • $1 \leq P_i \leq N$
  • $P_i \neq P_j$ 当 $i \neq j$
  • $P_1 = X$ 且 $P_{|P|} = Y$
  • 对于每个 $1 \leq i < |P|$，存在边连接 $P_i$ 和 $P_{i+1}$

题目保证这样的路径在约束条件下必然存在。

给定 $T$ 个测试用例，要求分别输出答案。

输入格式

  • 第一行包含整数 $T$ ($1 \leq T \leq 500$) —— 测试用例数
  • 对于每个测试用例：
    • 第一行包含两个整数 $N, M$ ($2 \leq N \leq 1000$, $N-1 \leq M \leq \min(\frac{N(N-1)}{2}, 5 \times 10^4)$)
    • 接下来 $M$ 行，每行两个整数 $U_i, V_i$ ($1 \leq U_i < V_i \leq N$)，无重复边
    • 最后一行两个整数 $X, Y$ ($1 \leq X, Y \leq N$, $X \neq Y$)

解题思路

可达鸭可达可达 详细分析

可达性分析：

  • 假设我们已经选了 $K$ 个点，对于剩下的点，是否会存在无法到达 $Y$ 点的情况？
  • 显然，若我们一个点都没选，根据题目限定图是连通的，必然可达 $Y$ 点。但由于路径必须是简单路径（顶点不重复），选了部分点后可能会出现无法到达 $Y$ 的情况。
  • 对这种情况需要进行剪枝。

剪枝策略：

  • 每当选定了一个顶点 $U$ 作为路径中的点时，建立一个 $\texttt{reach}$ 数组，从顶点 $Y$ 开始进行广度优先搜索（BFS）。
  • 对于能够被搜索到的点，我们标记为“可达”。（无向图中可达性是对称的，即若 $A$ 可达 $B$，则 $B$ 也可达 $A$）
  • 对于不可达的点，我们在后续选点时不考虑它们。
  • 最终在可达的顶点中选择字典序最小的点作为下一个路径点 $U$。

代码实现

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
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
/*

*/
void slu() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--;
    y--;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> vis(n, 0);
    vector<int> res, reach;
    while (1) {
        vis[x] = 1;
        res.push_back(x + 1);
        if (x == y) {
            break;
        }

        reach.assign(n, 0);
        queue<int> q;
        q.push(y);
        reach[y] = 1;

        while (!q.empty()) {
            int u = q.back();
            q.pop();
            for (auto v : adj[u]) {
                if (vis[v] || reach[v]) continue;
                reach[v] = 1;
                q.push(v);
            }
        }

        int t = n - 1;
        for (auto v : adj[x]) {
            if (!vis[v] && reach[v]) {
                t = min(t, v);
            }
        }

        x = t;
    }

    for (auto x : res) cout << x << " ";
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    cin >> t;

    while (t--) slu();
    return 0;
}



F. Random Gathering

题目链接：Problem F - Random Gathering
时间限制：3秒/测试用例
内存限制：1024MB

题目描述

有 $N$ 个盘子从左到右依次编号为盘子 $1$, 盘子 $2$, …, 盘子 $N$。初始时，第 $i$ 个盘子中有 $A_i$ 颗石子。

你将对这些盘子执行 $M$ 次操作。第 $i$ 次操作给出两个整数 $L_i$ 和 $R_i$，按顺序执行以下步骤：

  1. 从盘子 $L_i$ 到盘子 $R_i$（共 $R_i - L_i + 1$ 个盘子）中移除所有石子。
  2. 在区间 $[L_i, R_i]$ 内均匀随机选择一个整数 $x$。
  3. 将刚刚移除的所有石子放到盘子 $x$ 上。

在所有 $M$ 次操作执行完毕后，求每个盘子 $i$ 中石子的期望数量（对 $998244353$ 取模）。

输入格式

  • 第一行包含两个整数 $N, M$，满足 $1 \leq N, M \leq 2 \times 10^5$
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，满足 $0 \leq A_i < 998244353$（$1 \leq i \leq N$），表示每个盘子的初始石子数
  • 接下来 $M$ 行，每行包含两个整数 $L_i, R_i$，满足 $1 \leq L_i \leq R_i \leq N$（$1 \leq i \leq M$），表示第 $i$ 次操作的区间
  • 所有输入值均为整数

解题思路

西格玛树板子喵喵 详细分析

分析：

  • 操作1：移除Li-Ri之间的石子 ----> 区间置0
  • 操作2：获取移除的石子数目S -----> 区间求和
  • 操作3: 把移除的石子放到x上 <—>在本题背景下，由于要求期望，其实就是 对于每一个位置放 （移除总数）/（区间总长度）---->区间置换x

为什么选择线段树

  • 由于以上3种操作在线段树中都极其方便处理，并且 总数n小于2e5，也符合线段树的空间限制

代码实现

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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;
const int MOD = 998244353;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;

    LazySegmentTree() : n(0) {}

    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }

    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }

    void init(int n_, Info v_ = Info()) { init(std::vector(n_, v_)); }

    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }

    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }

    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }

    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v) { modify(1, 0, n, p, v); }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m, r, x, y);
    }

    Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); }

    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }

    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }

    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }

    void half() { half(1, 0, n); }

    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }

    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }

    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }

    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }

    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = std::max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }

    void maintainL() { maintainL(1, 0, n, -1); }

    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = std::max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }

    void maintainR() { maintainR(1, 0, n, -1); }
};

struct Tag {
    int x = 0;
    bool ok = false;

    void apply(const Tag &t) & {
        if (t.ok) x = t.x;
        ok |= t.ok;
    }
};

struct Info {
    int Sum = 0;
    int l = 0;
    bool act = false;

    void apply(const Tag &t) & {
        if (t.ok) {
            Sum = (l * t.x) % MOD;
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    if (!a.act) return b;
    if (!b.act) return a;
    Info res;

    res.l = a.l + b.l;
    res.Sum = (a.Sum + b.Sum) % MOD;
    res.act = true;
    // cout << "Res:sum: " << res.Sum << endl;

    return res;
}
int qpow(int a, int b, int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}
/*
rangeQuery(int l, int r)
*/
void slu() {
    int n, m;
    cin >> n >> m;
    vector<Info> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].Sum;
        a[i].act = true;
        a[i].l = 1;
    }
    LazySegmentTree<Info, Tag> tr(a);
    while (m--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int Len = r - l + 1;
        // cout << l << ' ' << r << ' ';
        int qSum = tr.rangeQuery(l, r + 1).Sum;

        // cout << qSum;
        qSum = (qSum * qpow(Len, MOD - 2, MOD)) % MOD;

        tr.rangeApply(l, r + 1, {qSum, true});

        // cout << "atf: " << qSum << endl;
    }
    for (int i = 0; i < n; i++) {
        cout << tr.rangeQuery(i, i + 1).Sum << " \n"[i == n - 1];
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}