{"problem":{"name":"「UOI-R1」求和","description":{"content":"给定 $n$ 个区间 $p_i, q_i$。 求$\\sum\\limits_{s_1={p_1}}^{q_1}\\sum\\limits_{s_2={p_2}}^{q_2}\\sum\\limits_{s_3={p_3}}^{q_3} \\cdots\\sum\\limits_{s_n={p_n}}^{q_n}\\max\\limits_{i=1}^ns_i$ 对 $998244353$ 取余的值。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8894"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 个区间 $p_i, q_i$。\n\n求$\\sum\\limits_{s_1={p_1}}^{q_1}\\sum\\limits_{s_2={p_2}}^{q_2}\\sum\\limits_{s_3={p_3}}^{q_3} \\cdots\\sum\\limits_{s_n={p_n}}^{q_n}\\max\\limits_{i=1}^ns_i$ 对 $998244353$ 取余的值。\n\n## Input\n\n第 $1$ 行，一个整数 $n$，表示区间数量。\n\n第 $2$ 至 $(n+1)$ 行，每行两个整数 $p_i,q_i$。\n\n## Output\n\n一个整数，表示答案。你需要将答案取余 $998244353$ 后输出。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n取 $s = \\{1, 2\\}, \\max\\limits_{i=1}^ns_i=2$。\n\n取 $s = \\{2, 2\\}, \\max\\limits_{i=1}^ns_i = 2$。\n\n取 $s = \\{3, 2\\}, \\max\\limits_{i=1}^ns_i = 3$。\n\n取 $s = \\{4, 2\\}, \\max\\limits_{i=1}^ns_i= 4$。\n\n取 $s = \\{1, 3\\}, \\max\\limits_{i=1}^ns_i=3$。\n\n取 $s = \\{2, 3\\}, \\max\\limits_{i=1}^ns_i = 3$。\n\n取 $s = \\{3, 3\\}, \\max\\limits_{i=1}^ns_i = 3$。\n\n取 $s = \\{4, 3\\}, \\max\\limits_{i=1}^ns_i= 4$。\n\n$2+2+3+4+3+3+3+4 = 24$。\n\n### 数据范围\n\n对于 $30\\%$ 的数据，保证 $n \\leq 8$，$p_i, q_i \\leq 10$。\n\n对于 $100\\%$ 的数据，保证 $1 \\leq n \\leq 5 \\times 10^3$，$1 \\leq p_i \\leq q_i \\leq 5 \\times 10^3$。有区间可能相同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8894","tags":["动态规划 DP","O2优化"],"sample_group":[["2\n1 4\n2 3","24"],["见文件附件的 sum2.in","见文件附件的 sum2.ans"]],"created_at":"2026-03-03 11:09:25"}}