{"problem":{"name":"「yyOI R1」youyou 的篡改（Hard Ver.）","description":{"content":"youyou 准备举办一场比赛，这场比赛有 $n$ 道题，每一道题都有一个难度值 $v_i$。 youyou 给出一个计数分量 $k(k\\le n)$，他认为，第 $x(x \\geq k)$ 道题的可做性 $a_x$ 应当是第 $1\\sim x$ 题所有题目中将难度值从小到大排序后难度较大的 $k$ 道题目难度值之和。 由于第 $1 \\sim k-1$ 题难度过于简单，youyou 不想考虑这","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9637"},"statements":[{"statement_type":"Markdown","content":"youyou 准备举办一场比赛，这场比赛有 $n$ 道题，每一道题都有一个难度值 $v_i$。\n\nyouyou 给出一个计数分量 $k(k\\le n)$，他认为，第 $x(x \\geq k)$ 道题的可做性 $a_x$ 应当是第 $1\\sim x$ 题所有题目中将难度值从小到大排序后难度较大的 $k$ 道题目难度值之和。\n\n由于第 $1 \\sim k-1$ 题难度过于简单，youyou 不想考虑这些题目的可做性。\n\n那么这场比赛的总可做性即为第 $k$ 道题至第 $n$ 道题可做性之和，即 $\\sum^{n}_{i=k}a_i$\n 的值。\n\n他可以篡改题目 $m$ 的难度为任意正整数。\n\n问：总可做性必须满足在区间 $[l,r]$ 的范围内，那么总可做性有几种取值？\n\n## Input\n\n第一行输入五个正整数，分别为 $n,m,k,l,r$。\n\n第二行输入 $n$ 个整数，第 $i$ 个数 $v_i$ 为第 $i$ 道题难度值。\n\n## Output\n\n仅一行，输出一个数，表示在满足条件的前提下，总可做性的取值数。\n\n[samples]\n\n## Background\n\n**Easy Version 与 Hard Version 仅最后所求内容不同，其他描述均一致。**\n\n## Note\n\n### 样例解释#1\n\n你可以改动 $v_1$，$k=1$。\n\n当第一个数改动为 $1$ 时，总难度 $1+2+2+2+2=9$。\n\n当第一个数改动为 $2$ 时，总难度 $2+2+2+2+2=10$。\n\n仅有以上两种取值符合题意，即总难度值等于 $9$ 或 $10$。因此答案为 $2$。\n\n## 数据范围\n\n本题启用 **Subtask**，对于每一个 **Subtask**，你需要通过全部测试点才能得到该部分的分数。\n\n| 子任务编号 | $n$ | 分数 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $\\le10$ | $15$ |\n| $2$ | $\\le10^3$ | $15$ |\n| $3$ | $\\le10^5$ | $70$ |\n\n对于 $100\\%$ 的数据，$1\\le k,t \\le n \\le 10^5$，$1 \\le l \\le r \\le 10^{9}$，$1\\le v_i\\le10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9637","tags":["O2优化"],"sample_group":[["5 1 1 5 10\n1 2 2 2 2","2"]],"created_at":"2026-03-03 11:09:25"}}