题解 #
本题要求的是在某一时刻前 k 小的优先级的和，所以我们不妨以优先级（要先离散化）为下标建立可持久化线段树（主席树），也就是说从任一根节点出发得到的是某一时刻正在运行的所有任务。这样一个任务可以被拆分成两个事件：
- 在 S 秒时加入正在运行的任务的集合（也就是在主席树上对应的优先级上 +1）
- 在 E+1 秒时从正在运行的任务的集合中移除（也就是在主席树上对应的优先级上 -1）
我们把所有事件按时间顺序排序并依次更新主席树，并记录对于每个时刻，该时刻前最新版本的线段树的根节点，查询时就从该根节点出发。
线段树要维护两个信息，一个是区间内正在运行任务的数量，一个是正在运行的任务的优先级之和。
值得注意的是查询的是单一时刻的信息，不像求区间第 k 小时要两个区间信息相减，所以写起来也简单一点。
一个非常容易错的地方是查询是当走到叶子节点时，如果该优先级的任务数量大于当前的 k 值，不能直接加上叶子节点中的优先级之和，要先除以任务数量再乘 k 值。
代码 #
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct PST {
int n, tot = 0;
struct node {
int lc, rc, cnt;
ll sum;
};
vector<node> t;
vector<int> roots; // left child, right child
PST(int n_) : n(n_), t(n << 6), roots(1) {
build(0, n - 1, roots[0]);
}
#define lc(rt) t[rt].lc
#define rc(rt) t[rt].rc
void pushup(int rt) {
t[rt].sum = t[lc(rt)].sum + t[rc(rt)].sum;
t[rt].cnt = t[lc(rt)].cnt + t[rc(rt)].cnt;
}
void build(int l, int r, int &rt) {
rt = ++tot;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, lc(rt));
build(mid + 1, r, rc(rt));
pushup(rt);
}
void update(int pos, int dcnt, int dsum, int l, int r, int old, int &rt) {
rt = ++tot;
t[rt] = t[old];
if (l == r) {
t[rt].cnt = t[old].cnt + dcnt;
t[rt].sum = t[old].sum + dsum;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, dcnt, dsum, l, mid, lc(old), lc(rt));
else update(pos, dcnt, dsum, mid + 1, r, rc(old), rc(rt));
pushup(rt);
}
int update(int pos, int dcnt, int dsum) { // return the root of the new version
int new_root;
update(pos, dcnt, dsum, 0, n - 1, roots.back(), new_root);
roots.push_back(new_root);
return new_root;
}
ll query(int v, int l, int r, int k) {
if (l == r)
return (t[v].cnt > k ? t[v].sum / t[v].cnt * k : t[v].sum);
int mid = (l + r) / 2, x = t[lc(v)].cnt;
ll sum = t[lc(v)].sum;
if (k <= x) return query(lc(v), l, mid, k);
return sum + query(rc(v), mid + 1, r, k - x);
}
ll query(int v, int k) { return query(v, 0, n - 1, k); }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<tuple<int, int, int>> tasks(n);
vector<int> p; // 所有的优先级，用于离散化
for (auto &[s, e, pp] : tasks) {
cin >> s >> e >> pp;
p.push_back(pp);
}
sort(begin(p), end(p));
p.erase(unique(begin(p), end(p)), end(p)); // 离散化
vector<pair<int, int>> events;
for (auto [s, e, pp] : tasks) {
int id = lower_bound(begin(p), end(p), pp) - begin(p);
// 两个事件，用优先级的正负来表示加入或者删除
events.emplace_back(s, id + 1);
events.emplace_back(e + 1, -id - 1);
}
sort(begin(events), end(events));
PST tr(size(p));
vector<int> roots(n + 1); // root[i] 代表 i 时刻前最新的线段树的版本
roots[0] = 1;
for (auto [time, id] : events) {
if (id > 0) {
roots[time] = (tr.update(id - 1, 1, p[id - 1]));
} else {
id = -id - 1;
roots[time] = (tr.update(id, -1, -p[id]));
}
}
for (int i = 1; i <= n; i++)
// 对于没有事件发生的时刻 i，其最新的版本为上一时刻的最新版本
if (!roots[i]) roots[i] = roots[i - 1];
ll pre = 1;
while (q--) {
int x, a, b, c;
cin >> x >> a >> b >> c;
auto k = 1 + (a * pre + b) % c;
auto res = tr.query(roots[x], k);
cout << res << '\n';
pre = res;
}
}