← 返回题目列表

Codeforces · 2173/F

F. Isla 的内存阈值

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

我希望有一天,你能与你珍惜的人重聚。
— 可塑性记忆

在世界上 可塑性记忆,Isla 正在收集 $$$n$$$ 内存碎片。第 $$$i$$$ 片段的大小为 $$$a_i$$$,大小为 非增加,即 $$$a_1 \ge a_2 \ge \cdots \ge a_n$$$。

在检索期间,Isla 处理一定范围内的片段并将其大小存储到缓冲区中。每当缓冲区达到给定阈值 $$$x$$$ 时,就会溢出:记录一个胶囊,并将缓冲区清零。

有 $$$q$$$ 独立查询,每个查询由三元组 $$$(l,r,x)$$$ 描述。对于每个查询,$$$x$$$ 表示 Isla 的内存容量。然后 Isla 为每个 $$$l \le i \le r$$$ 逐一拾取第 $$$i$$$ 个内存片段。在任何时刻,如果她当前持有的碎片的总大小至少为$$$x$$$,她就会完全清除她的记忆(什么都不保留)。你必须确定艾拉清除记忆的次数以及她所持有的碎片大小的最终总和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 150,000$$$) — $$$a$$$ 的长度和查询数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — $$$a$$$ 的元素。保证 $$$a_1 \ge a_2 \ge \cdots \ge a_n$$$。

接下来是 $$$q$$$ 行,每行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^9$$$) — 一个查询。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$150,000$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$150,000$$$。

输出

对于每个测试用例,为每个查询输出两个整数——Isla 清除内存的次数以及她持有的片段大小的最终总和。

示例

输入
复制

3
5 4
7 5 5 2 1
1 3 10
2 5 6
1 5 7
3 5 4
6 5
6 6 5 3 2 2
1 6 2
1 6 7
2 6 7
2 5 4
2 5 3
11 7
938412006 792864920 746880066 729862150 704473377 550436315 381392172 326088331 316506801 301443698 190862681
1 3 417253102
9 11 857592497
1 11 344359921
1 7 408760015
8 8 544749974
7 10 361090133
3 11 888178376

输出
复制

1 5
1 3
2 3
1 3
6 0
2 4
2 0
3 0
3 2
3 0
0 808813180
9 0
6 381392172
0 326088331
2 301443698
3 492306379

注意

设 $$$\texttt{cnt}$$$ 为 Isla 清除记忆的次数,$$$\texttt{sum}$$$ 为她持有的碎片的总大小。

在第一个测试用例中,对于第一个查询 $$$(l, r, x) = (1, 3, 10)$$$:

  • 以 $$$\texttt{sum}=0$$$ 开头;
  • 添加 $$$a_1=7 \Rightarrow \texttt{sum}=7$$$ (仍然是 $$$\lt 10$$$);
  • 添加 $$$a_2=5 \Rightarrow \texttt{sum}=12 \ge 10 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 1$$$;
  • 添加 $$$a_3=5 \Rightarrow \texttt{sum}=5$$$。

因此,我们打印 $$$\texttt{cnt}=1$$$ 和 $$$\texttt{sum}=5$$$。

在第二个测试用例中,对于第五个查询 $$$(l, r, x) = (2, 5, 3)$$$:

  • 以 $$$\texttt{sum}=0$$$ 开头;
  • 添加 $$$a_2=6 \Rightarrow \texttt{sum}=6 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 1$$$;
  • 添加 $$$a_3=5 \Rightarrow \texttt{sum}=5 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 2$$$;
  • 添加 $$$a_4=3 \Rightarrow \texttt{sum}=3 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 3$$$;
  • 添加 $$$a_5=2 \Rightarrow \texttt{sum}=2$$$ (仍然是 $$$\lt 3$$$);
因此,我们打印 $$$\texttt{cnt}=3$$$ 和 $$$\texttt{sum}=2$$$。