题目理解

我们有 $m$ 个任务，每个任务在时间段 $[S_i, E_i]$ 内运行，优先级为 $P_i$。 有 $n$ 次查询，每次查询给定时间 $X_i$，要求求出该时刻正在运行的任务中，优先级最小的 $K_i$ 个任务的优先级之和。 $K_i$ 由公式 $K_i = 1 + (A_i \cdot Pre + B_i) \bmod C_i$ 计算，$Pre$ 是上一次查询结果。

核心难点

每个时刻运行的任务集合不同。

需要快速查询前 $K$ 小的优先级之和。

直接对每个时刻建一个列表会超时（$n$ 可达 $10^5$，$m$ 可达 $10^5$）。

解题思路

1. 时间轴扫描 + 差分思想

每个任务 $(S_i,E_i,P_i)$ 可以看作：

在 $S_i$ 时刻加入任务 $i$（优先级 $P_i$）

在 $E_i+1$ 时刻移除任务 $i$

这样我们按时间顺序处理，就可以维护当前运行的任务集合。

2. 可持久化权值线段树

为了能够查询任意时刻 $X_i$ 的任务情况，我们使用可持久化线段树：

对时间 $t=1$ 到 $n$ 依次建立版本

每个版本在上一个版本基础上，应用该时刻的加入/删除操作

线段树下标是优先级的离散化值，节点存储：

该区间内任务数量 c

该区间内任务优先级之和 S

3. 操作流程

1.离散化优先级：将 $P_i$ 映射到 $1 \dots o$。

2.建立事件：v[s].push_back({i, 1}) 表示在 $s$ 时刻加入任务 $i$；v[e+1].push_back({i, -1}) 表示在 $e+1$ 时刻移除任务 $i$。

3.构建可持久化线段树：

从 $t=1$ 到 $n$，以 $r[t-1]$ 为上一版本，处理 $v[t]$ 中的所有事件（+1 或 -1），得到新版本 $r[t]$。

4.查询：

对查询 $(X_i, A_i, B_i, C_i)$，先计算 $K_i$。

在版本 $r[X_i]$ 的线段树中查询前 $K_i$ 小的优先级和。

查询方法

在线段树节点 $[l,r]$ 上：

如果 $k \le tr[左子节点].c$，则递归左子树

否则，答案 = 左子树优先级和 + 递归右子树（$k$ 减去左子树任务数）

复杂度分析

离散化：$O(m \log m)$

建树：$O(m \log m)$，每个任务产生 2 次更新

查询：$O(\log m)$ 每次

总复杂度：$O((m+n) \log m)$

代码关键点

tr[i].c：区间任务数

tr[i].S：区间优先级和

G 函数：可持久化更新

Q 函数：查询前 $k$ 小和

用 vector v[] 存每个时间点的事件

总结

本题结合了时间轴扫描、可持久化线段树和前 k 小和查询，是一道比较经典的数据结构综合题，考察对可持久化结构的理解和应用。