注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++

请在提交源代码前添加 #include "koninc.h"。

题目描述

题目译自 XX Olimpiada Informatyczna — II etap Konewka

你被任命为 Bajtolina 女王的园丁，倍感荣幸，对吧？但这份工作的挑战远不止表面光鲜。女王的城堡旁有一座巨大的花园，种植了 $n$ 棵依次排列的树木。看似简单，但你必须随时向女王汇报哪些树木已经成熟——我们规定，树木高度达到至少 $k$ 米时即为成熟。

女王不时要求你用魔法洒水壶为某些树木浇水，每次浇水使受影响的树木高度增加正好 $1$ 米。快证明你的能力，迅速回应女王的所有询问吧！

交互方式

你需要编写一个与评测程序交互的库，至少包含以下三个函数，供评测程序调用：

• inicjuj(n, k, D)：此函数在评测开始时调用一次，用于初始化你的数据结构。参数包括树木数量 $n$、成熟高度下限 $k$ 和长度为 $n$ 的数组 $D$，存储每棵树的初始高度。树木编号为 $0$ 至 $n-1$。
  • C/C++: void inicjuj(int n, int k, int *D);
  • Pascal: procedure inicjuj(n, k: LongInt; var D: array of LongInt);
• podlej(a, b)：表示女王要求你浇灌从第 $a$ 棵到第 $b$ 棵树（包含两端，$0 \leq a \leq b \leq n-1$）。调用此函数后，这些树木高度各增加 $1$ 米。
  • C/C++: void podlej(int a, int b);
  • Pascal: procedure podlej(a, b: LongInt);
• dojrzale(a, b)：女王询问从第 $a$ 棵到第 $b$ 棵树（包含两端，$0 \leq a \leq b \leq n-1$）中有多少棵树已成熟。
  • C/C++: int dojrzale(int a, int b);
  • Pascal: function dojrzale(a, b: LongInt): LongInt;

你的库不得读取任何数据（包括标准输入或文件），也不得向文件或标准输出写入内容。可向标准错误输出（stderr）写入诊断信息，但需注意这会消耗时间。

若使用 C/C++，库不得包含 main 函数。若使用 Pascal，需提供模块（参考你的磁盘上的示例程序）。

只有当你的库满足上述技术要求并正确回答女王的所有询问时，测试才会得分。

编译与运行

你的库文件（kon.c、kon.cpp 或 kon.pas）将与评测程序一起编译，使用以下命令：

• C: gcc -O2 -static -lm kon.c kongrader.c -o kon
• C++: g++ -O2 -static -lm kon.cpp kongrader.cpp -o kon
• Pascal:
  ppc386 -O2 -XS -Xt kon.pas
ppc386 -O2 -XS -Xt kongrader.pas
mv kongrader kon

样例

示例评测程序

「文件」下包含示例评测程序（kongrader.c、kongrader.cpp、kongrader.pas）。要运行评测程序，需将你的库命名为 kon.c、kon.cpp 或 kon.pas，放入对应目录（c、cpp 或 pas）。比赛开始时，这些目录包含示例的错误代码。使用以下命令编译评测程序与你的库：

make kon

此命令与「编译与运行」的描述一致。C/C++ 编译需包含 koninc.h 文件，位于对应目录。

编译后的评测程序从标准输入读取输入数据，调用你的库函数，并将结果输出到标准输出。

输入数据格式如下：

第一行包含两个整数 $n, k$。

第二行包含 $n$ 个整数，表示各树初始高度。

第三行包含一个整数 $q$。

接下来的 $q$ 行，每行包含一个字母（p 或 d）和两个非负整数。字母表示调用函数：p 为 podlej，d 为 dojrzale；数字为函数参数。函数 inicjuj 在读取前两行后立即调用。注意，示例评测程序不验证输入格式或限制条件。

「文件」下包含文件 kon0.in，对应上述样例运行。使用以下命令运行：

./kon < kon0.in

函数 dojrzale 的结果将输出到标准输出。正确结果在文件 kon0.out 中。

附加样例

1. $n=2000$，podlej 和 dojrzale 调用总数为 $10000$，均针对单棵树，初始高度随机从 $[1, 100]$，$k=100$。
2. $n=100000$，先 $100000$ 次 podlej 调用，覆盖所有树，后 $100000$ 次 dojrzale 调用，针对单棵树，初始高度随机从 $[1, 1000]$，$k=100500$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 300000$，
• $1 \leq k \leq 10^9$，
• 函数 podlej 和 dojrzale 的总调用次数不超过 $300000$，
• 树木初始高度为不超过 $10^9$ 的正整数。

对于 $20\%$ 的测试数据，$n \leq 2000$，且 podlej 和 dojrzale 调用总数 $\leq 10000$。
对于 $70\%$ 的测试数据，所有 podlej 调用先于 dojrzale 调用。