[洛谷P3168][CQOI2015]任务查询系统

题目大意：有$n$个任务，第$i$个任务存在于$[l_i,r_i]$，优先级为$p_i$，$m$个询问，每个问在$x_i$时刻时，优先级最小的$k$个的优先级的和是多少。

题解：离散化优先级，前缀和主席树即可

卡点：1~4.数组开小一倍，$root$数组未连续

C++ Code：

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 100010
#define N maxn * 40
#define int long long
struct 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
", lastans = sum[root[x]]);
		else printf("%lld
", lastans = ask(root[x], 1, M, k));
	}
	return 0;
}