Luogu P3168 [CQOI2015]任务查询系统

题目链接 \(Click\) \(Here\)

差分主席树，就是把主席树做成一个差分前缀和的形式，还是很容易想到的。

写主席树的时候几个注意点：

• 查询可能开始于所有任务之前，二分任务点要把左边界设置为\(0\)
• 记得开\(longlong\)
• 主席树通用细节：查询结束后的边界可能有残余答案未统计。即一个权值里的数，选了太多，不选太少，二分后要手动选上漏掉的部分。

#include <bits/stdc++.h>
using namespace std;const int N = 200010;
const int INF = 1e7;#define int long longint m, n, pre = 1;struct Task {
int t, w, p;
bool operator < (Task rhs) const {
return t < rhs.t;
}
}task[N << 1];int tot = 1, rt[N << 1];
#define mid ((l + r) >> 1)struct Segment_Node {
int sz, ls, rs, sum;
}t[N << 6];int modify (int _rt, int l, int r, int w, int del) {
int p = ++tot;
t[p].sz = t[_rt].sz + del;
t[p].sum = t[_rt].sum + del * w;
if (l != r) {
if (w <= mid) {
t[p].ls = modify (t[_rt].ls, l, mid, w, del), t[p].rs = t[_rt].rs;
} else {
t[p].rs = modify (t[_rt].rs, mid + 1, r, w, del), t[p].ls = t[_rt].ls;
}
} else {
t[p].ls = t[p].rs = 0;
}
return p;
}int query (int rt, int l, int r, int k) {
int sum = 0; k = min (k, t[rt].sz);
while (l < r) {
int lch = t[t[rt].ls].sz;
int lsum = t[t[rt].ls].sum;
if (k >= lch) {
k -= lch;
sum += lsum;
l = mid + 1;
rt = t[rt].rs;
} else {
r = mid;
rt = t[rt].ls;
}
}
return sum + k * r;
}
#undef midsigned main () {
// freopen ("data.in", "r", stdin);
// freopen ("data.out", "w", stdout);
t[0] = (Segment_Node) {0, 0, 0, 0};
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
static int S, E, P;
cin >> S >> E >> P;
task[i * 2 - 1] = (Task) {S, +1, P};
task[i * 2] = (Task) {E + 1, -1, P};
}
sort (task + 1, task + 1 + m * 2);
for (int i = 1; i <= m * 2; ++i) {
rt[i] = modify (rt[i - 1], 1, 1e7, task[i].p, task[i].w);
// printf ("task[%d] = {%d, %d, %d}\n", i, task[i].t, task[i].w, task[i].p);
}
for (int i = 1; i <= n; ++i) {
static int X, K, A, B, C;
cin >> X >> A >> B >> C;
K = 1 + (A * pre + B) % C;
int l = 0, r = m * 2;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (task[mid].t <= X) {
l = mid;
} else {
r = mid - 1;
}
}
// printf ("l = %d, k = %d\n", l, K);
    cout << (pre = query (rt[l], 1, 1e7, K)) << endl;
}
}