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 long

int 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 mid

signed 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;
    }
}

Luogu P3168 [CQOI2015]任务查询系统

原文：https://www.cnblogs.com/maomao9173/p/10550468.html