题目大意：有$n$个任务，第$i$个任务存在于$[l_i,r_i]$，优先级为$p_i$，$m$个询问，每个问在$x_i$时刻时，优先级最小的$k$个的优先级的和是多少。
题解：离散化优先级，前缀和主席树即可
卡点：1~4.数组开小一倍，$root$数组未连续
C++ Code：
#include#include #include #define maxn 100010#define N maxn * 40#define int long longstruct Modify { int r, val, tg; inline bool operator < (const Modify &rhs) const { return r < rhs.r; }} Q[maxn << 1];int n, m, lastans = 1, ans;int V[maxn];int root[maxn], idx;int lc[N], rc[N], sz[N], sum[N];void add(int &rt, int l, int r, int p, int tg) { lc[++idx] = lc[rt], rc[idx] = rc[rt], sz[idx] = sz[rt], sum[idx] = sum[rt], rt = idx; sz[rt] += tg; sum[rt] += tg * V[p]; if (l != r) { int mid = l + r >> 1; if (p <= mid) add(lc[rt], l, mid, p, tg); else add(rc[rt], mid + 1, r, p, tg); }}int ask(int rt, int l, int r, int k) { if (l == r) return V[l] * k; int mid = l + r >> 1; if (sz[lc[rt]] >= k) return ask(lc[rt], l, mid, k); else return sum[lc[rt]] + ask(rc[rt], mid + 1, r, k - sz[lc[rt]]);}signed main() { scanf("%lld%lld", &m, &n); for (int i = 0; i < m; i++) { int a, b, c; scanf("%lld%lld%lld", &a, &b, &c); Q[i << 1] = (Modify) {a, c, 1}; Q[i << 1 | 1] = (Modify) {b + 1, c, -1}; V[i + 1] = c; } std::sort(V + 1, V + m + 1); int M = std::unique(V + 1, V + m + 1) - V + 1; std::sort(Q, Q + (m << 1)); int lastnum = 0; root[0] = idx = 1; for (int i = 0; i < m << 1; i++) { int x = Q[i].r; if (!root[x]) { for (int i = lastnum + 1; i <= x; i++) root[i] = root[lastnum]; lastnum = x; } add(root[x], 1, M, std::lower_bound(V + 1, V + M + 1, Q[i].val) - V, Q[i].tg); } while (n --> 0) { int x, a, b, c, k; scanf("%lld%lld%lld%lld", &x, &a, &b, &c); k = (a * lastans + b) % c + 1; if (k >= sz[root[x]]) printf("%lld\n", lastans = sum[root[x]]); else printf("%lld\n", lastans = ask(root[x], 1, M, k)); } return 0;}