← 返回题目列表

AtCoder · arc220_c

C. 范围增量

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你整数 N,M,K 和一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。保证每个元素 A 介于 0 和 M-1,包括在内。

您可以对整数序列执行以下操作 A 之间 0 和 K 次,包括:

  • 选择一对整数 (l,r) 满意 1\le l\le r\le N,并替换 A_k 与 (A_k+1) \bmod M 对于每个 k=l,l+1,\ldots,r.

查找字典顺序最小的 A 操作后。

你被给予 T 测试用例;解决它们中的每一个。

序列的字典顺序是什么?

一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果满足以下条件之一。 在这里, |S| 和 |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两项成立。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i (在数值上)小于 T_i.

约束

  • 1\le T\le 3\times 10^5
  • 1\le N\le 3\times 10^5
  • 2\le M\le 10^9
  • 1\le K\le 10^{15}
  • 0\le A_i < M
  • 总和 一个输入文件中的 N 所有测试用例最多 3\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N M K
A_1 A_2 \ldots A_N

输出

按顺序输出测试用例的答案,以换行符分隔。

对于每个测试用例,输出字典顺序最小的元素 A 运算后,用空格分隔。


示例输入 1

3
4 6 3
2 5 4 1
4 17 100
2 0 2 6
5 10 6
2 6 5 3 9

示例输出 1

2 0 0 1
0 0 0 0
2 0 0 3 0

考虑第一个测试用例。

通过执行如下两个操作,我们可以得到 A=(2,0,0,1).

  • 操作 1:选择 (l,r)=(2,3)。现在 A=(2,0,5,1).
  • 操作 2:选择 (l,r)=(3,3)。现在 A=(2,0,0,1).