310139: CF1787I. Treasure Hunt
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Treasure Hunt
题意翻译
### 题目描述 定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。 例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。 给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。 输出对 $998\,244\,353$ 取模。 ### 输入格式 第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。 ### 输出格式 对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。 ### 样例解释 第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。 第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。题目描述
Define the beauty value of a sequence $ b_1,b_2,\ldots,b_c $ as the maximum value of $ \sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i $ , where $ q $ , $ s $ , $ t $ are all integers and $ s > q $ or $ t\leq q $ . Note that $ b_i = 0 $ when $ i<1 $ or $ i>c $ , $ \sum\limits_{i=s}^{t}b_i = 0 $ when $ s>t $ . For example, when $ b = [-1,-2,-3] $ , we may have $ q = 0 $ , $ s = 3 $ , $ t = 2 $ so the beauty value is $ 0 + 0 = 0 $ . And when $ b = [-1,2,-3] $ , we have $ q = s = t = 2 $ so the beauty value is $ 1 + 2 = 3 $ . You are given a sequence $ a $ of length $ n $ , determine the sum of the beauty value of all non-empty subsegments $ a_l,a_{l+1},\ldots,a_r $ ( $ 1\leq l\leq r\leq n $ ) of the sequence $ a $ . Print the answer modulo $ 998\,244\,353 $ .输入输出格式
输入格式
Each test contains multiple test cases. The first line contains an integer $ T $ ( $ 1 \le T \le 10^4 $ ) — the number of test cases. The first line contains an integer $ n $ ( $ 1\le n\le 10^6 $ ) — the length of $ a $ . The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -10^6 \leq a_i \leq 10^6 $ ) — the given sequence. It's guaranteed that the sum of $ n $ does not exceed $ 10^6 $ .
输出格式
For each test case, print a line containing a single integer — the answer modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
4
7
80 59 100 -52 -86 -62 75
8
-48 -14 -26 43 -41 34 13 55
1
74
20
56 -60 62 13 88 -48 64 36 -10 19 94 25 -69 88 87 79 -70 74 -26 59输出样例 #1
5924
2548
148
98887说明
In the second test case, for the subsequence $ [-26,43,-41,34,13] $ , when $ q=5 $ , $ s=2 $ , $ t=5 $ , $ \sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72 $ . In the third test case, there is only one non-empty consecutive subsequence $ [74] $ . When $ q=1 $ , $ s=1 $ , $ t=1 $ , $ \sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148 $ .Input
题意翻译
### 题目描述 定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。 例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。 给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。 输出对 $998\,244\,353$ 取模。 ### 输入格式 第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。 ### 输出格式 对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。 ### 样例解释 第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。 第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。Output
**寻宝游戏**
### 题目描述
定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。
例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。
给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。
输出对 $998\,244\,353$ 取模。
### 输入格式
第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。
每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。
第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。
### 输出格式
对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。
### 样例解释
第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。
第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。**寻宝游戏** ### 题目描述 定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。 例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。 给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。 输出对 $998\,244\,353$ 取模。 ### 输入格式 第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。 ### 输出格式 对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。 ### 样例解释 第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。 第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。
### 题目描述
定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。
例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。
给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。
输出对 $998\,244\,353$ 取模。
### 输入格式
第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。
每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。
第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。
### 输出格式
对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。
### 样例解释
第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。
第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。**寻宝游戏** ### 题目描述 定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $i<1$ 或 $i>c$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。 例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。 给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子序列 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。 输出对 $998\,244\,353$ 取模。 ### 输入格式 第一行一个正整数 $T$（$1\le T\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 10^6$）表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6 \leq a_i \leq 10^6$）表示序列 $a$。 ### 输出格式 对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。 ### 样例解释 第二组测试数据中，对于子序列 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。 第三组测试数据中，只有一个子序列 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。