「MXOI Round 2」排名

Luogu
IDLGP9587
Time1000ms
Memory512MB
DifficultyP3
动态规划 DP贪心洛谷原创O2优化排序前缀和洛谷月赛
小 C 有一个长度为 $n$ 的数组 $a$。 小 C 定义,$f(i)$ 为 $a_i$ 的前排名,其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。 小 C 还定义,$g(i)$ 为 $a_i$ 的后排名,其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。 每次操作,小 C 需要选择一个不大于 $n$ 的正整数 $t$,并将 $a_t$ 的值增加 $1$。 小 C 想知道,对于每一个 $1 \le i \le n$,想要使 $f(i) \le k \le g(i)$,最少需要进行多少次操作? 可以证明一定存在至少一种操作方案使得 $f(i) \le k \le g(i)$。 ## Input 第一行三个整数 $c,n,k$,其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。 第二行 $n$ 个整数,表示给定的数组 $a$。 ## Output 共 $n$ 行,每行一个整数,其中第 $i$ 行的整数表示想要使 $f(i) \le k \le g(i)$ 所至少需要进行的操作数。 [samples] ## Note #### 【样例解释 #1】 当 $i=1$ 时,小 C 可以选择 $t=1$ 并进行 $3$ 次操作。此时 $f(i)=2$,$g(i)=4$,满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $3$ 次操作。 当 $i=4$ 时,小 C 可以选择 $t=3$ 进行 $1$ 次操作,再选择 $t=6$ 进行 $1$ 次操作。此时 $f(i)=1$,$g(i)=3$,满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $2$ 次操作。 #### 【样例 #2】 见附加文件中的 `rank/rank2.in` 与 `rank/rank2.ans`。 该样例满足测试点 $7$ 的限制。 #### 【样例 #3】 见附加文件中的 `rank/rank3.in` 与 `rank/rank3.ans`。 该样例满足测试点 $20$ 的限制。 #### 【数据范围】 对于 $100\%$ 的数据,$1 \le k \le n \le 5 \times 10^5$,$1 \le a_i \le 10^9$。 |测试点编号|$n \le$|$a_i \le$|特殊性质| |:---:|:---:|:---:|:---:| |$1\sim6$|$2000$|$10^9$|A| |$7\sim10$|$2000$|$10^9$|无| |$11\sim14$|$5\times10^5$|$10^9$|B| |$15\sim20$|$5\times10^5$|$10^9$|无| 特殊性质 A:保证对于所有的 $1 \le i \lt n$,都有 $a_i \ge a_{i+1}$。 特殊性质 B:保证 $k=1$。
Samples
Input #1
0 6 3
1 1 4 5 1 4
Output #1
3
3
0
2
3
0
API Response (JSON)
{
  "problem": {
    "name": "「MXOI Round 2」排名",
    "description": {
      "content": "小 C 有一个长度为 $n$ 的数组 $a$。 小 C 定义,$f(i)$ 为 $a_i$ 的前排名,其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。 小 C 还定义,$g(i)$ 为 $a_i$ 的后排名,其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。 每次操作,小 C 需要选择一个不大于 $n$ 的正整数 $t$,并将 $a_t",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9587"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 C 有一个长度为 $n$ 的数组 $a$。\n\n小 C 定义,$f(i)$ 为 $a_i$ 的前排名,其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。\n\n小 C 还定义,$g(i)$ 为 $a_i$ 的后排名,其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。\n\n每次操作,小 C 需要选择一个不大于 $n$ 的正整数 $t$,并将 $a_t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments