差分主席树，就是把主席树做成一个差分前缀和的形式，还是很容易想到的。
写主席树的时候几个注意点：
- 查询可能开始于所有任务之前，二分任务点要把左边界设置为\(0\)
- 记得开\(longlong\)
- 主席树通用细节：查询结束后的边界可能有残余答案未统计。即一个权值里的数，选了太多，不选太少，二分后要手动选上漏掉的部分。
#includeusing 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; }}