#P11875. [2023年联测]环日加速器
[2023年联测]环日加速器
题目描述
本题是库交互题。给定正整数 ,维护一个可重集合,其中每个元素是三元组 ,满足 。 是抽象信息,信息的合并运算可以交换、结合,并且存在单位元。
集合初始有 个元素,按给出的顺序编号为 。随后有 次操作。
- 加入一个新的三元组 。其编号为此前已经分配过的最大编号加 ,已删编号不复用。
- 删除指定编号 的元素,保证这个元素仍在集合中。
- 给定位置 ,返回将所有满足 的当前元素的 合并所得的结果。没有符合条件的元素时返回单位元。
提交接口
包含头文件 accelerator.h,实现以下函数,由交互库调用。交互库负责主函数与标准输入输出。
void init(int sid, int n, std::vector<std::tuple<int, int, Data>> S);
void modifyAdd(int l, int r, Data x);
void modifyDel(int k);
Data query(int k);
init仅在开始时调用一次。 是子任务编号, 给出初始元素,按照给出的顺序从 开始编号。modifyAdd、modifyDel、query分别处理加入、删除、查询。Data支持复制构造与赋值。静态函数Data::e()返回单位元。表达式x + y返回两个信息合并后的结果。
任意时刻存在的 Data 对象数量不能超过 。初始化最多合并 次。一次加入或删除最多合并 次。一次查询最多合并 次。
样例交互库
原题提供样例用的头文件与 grader.cpp。实际评测库的实现可能不同,提交程序应仅使用上述接口。
原样例交互库从标准输入读取数据。第一行是 ,第二行是 。接下来 行,每行五个整数 ,后三个整数一起表示初始信息 。再接下来 行,每行表示一次操作。
1 l r a b c表示加入,其中 一起表示 。2 k表示删除编号 。3 k表示查询位置 。
原样例库会把每次查询的结果显示为三个整数 。本站评测库从提交程序的返回值计算判题摘要,提交代码无需输出摘要。
原样例见下发目录中的 accelerator/accelerator1.in/out、accelerator/accelerator2.in/out、accelerator/accelerator3.in/out。后两个样例分别满足子任务 和 的限制。
数据范围
。
| 子任务 | 上界 | 特殊限制 | 本站分值 | |||
|---|---|---|---|---|---|---|
| 1 | 1000 | 200 | 2000 | 20 | ||
| 2 | 100 | |||||
| 3 | 50 | 80 | 没有删除 | |||
| 4 | ||||||
| 5 |
原赛分值为 ,上表按本站当前配置列出分值。