#P11875. [2023年联测]环日加速器

    ID: 11026 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600数据结构线段树分治图论动态规划数学构造

[2023年联测]环日加速器

题目描述

本题是库交互题。给定正整数 nn,维护一个可重集合,其中每个元素是三元组 (l,r,x)(l,r,x),满足 1≤l≤r≤n1\le l\le r\le n。xx 是抽象信息,信息的合并运算可以交换、结合,并且存在单位元。

集合初始有 mm 个元素,按给出的顺序编号为 1,…,m1,\ldots,m。随后有 qq 次操作。

  1. 加入一个新的三元组 (l,r,x)(l,r,x)。其编号为此前已经分配过的最大编号加 11,已删编号不复用。
  2. 删除指定编号 kk 的元素,保证这个元素仍在集合中。
  3. 给定位置 kk,返回将所有满足 l≤k≤rl\le k\le r 的当前元素的 xx 合并所得的结果。没有符合条件的元素时返回单位元。

提交接口

包含头文件 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 仅在开始时调用一次。sidsid 是子任务编号,SS 给出初始元素,按照给出的顺序从 11 开始编号。
  • modifyAdd、modifyDel、query 分别处理加入、删除、查询。
  • Data 支持复制构造与赋值。静态函数 Data::e() 返回单位元。表达式 x + y 返回两个信息合并后的结果。

任意时刻存在的 Data 对象数量不能超过 MM。初始化最多合并 mT1mT_1 次。一次加入或删除最多合并 T1T_1 次。一次查询最多合并 T2T_2 次。

样例交互库

原题提供样例用的头文件与 grader.cpp。实际评测库的实现可能不同,提交程序应仅使用上述接口。

原样例交互库从标准输入读取数据。第一行是 sid,M,T1,T2sid,M,T_1,T_2,第二行是 n,m,qn,m,q。接下来 mm 行,每行五个整数 l,r,a,b,cl,r,a,b,c,后三个整数一起表示初始信息 xx。再接下来 qq 行,每行表示一次操作。

  • 1 l r a b c 表示加入,其中 a,b,ca,b,c 一起表示 xx。
  • 2 k 表示删除编号 kk。
  • 3 k 表示查询位置 kk。

原样例库会把每次查询的结果显示为三个整数 a,b,ca,b,c。本站评测库从提交程序的返回值计算判题摘要,提交代码无需输出摘要。

原样例见下发目录中的 accelerator/accelerator1.in/out、accelerator/accelerator2.in/out、accelerator/accelerator3.in/out。后两个样例分别满足子任务 11 和 33 的限制。

数据范围

1≤n,m,q≤1051\le n,m,q\le10^5。

子任务 n,m,qn,m,q 上界 T1T_1 T2T_2 MM 特殊限制 本站分值
1 1000 200 2000 10710^7 20
2 10510^5 100
3 50 80 5×1055\times10^5 没有删除
4 10710^7
5 5×1055\times10^5

原赛分值为 10,20,20,20,3010,20,20,20,30,上表按本站当前配置列出分值。

原 PDF 题面