P3168 [CQOI2015]任务查询系统

题目地址：P3168 [CQOI2015]任务查询系统

主席树的模板题

更模板的在这儿：P3834 【模板】可持久化线段树 1（主席树）

形象的说，P3834是“单点修改，区间查询”，P3168是“区间修改，单点查询”

注意！这里只是形象的说，实际上两道题都是静态的

我们联想其他的“区间修改，单点查询”问题，我们都是怎么做的？

差分！

没错，差分，将“区间修改”改成“左端点加，右端点的右边减”的“单点修改”

那么，我们每次“单点查询”就相当于求前缀和，也就是一个“区间查询”

于是我们成功的将P3168转化成了P3834，然后就简单了

几个注意点：

公式 \(K_i=1+(A_i*Pre+B_i)\ mod\ C_i\) 会爆 int，注意开 long long
需要先进行离散化， \(sort+unique\) 即可
主席树要开 \(2*N\ log\ N\) ，其中 \(2\) 是因为差分以后“单点修改”的数量为原来“区间修改”的两倍（我的代码中直接将 N 扩大了一倍）
不要修改第 \(n+1\) 个区间，即修改到第 \(n+1\) 个区间就可以直接 break
在询问到 \(l==r\) 时不能直接返回 \(sum\) 而要返回 \(t[p].s / t[p].c * k\)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 6;
int n, m, pre = 1, b[N], rt[N], tot;
pii a[N];
struct T {
    int l, r, c, s;
} t[N*20];

int build(int l, int r) {
    int p = ++tot;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    t[p].l = build(l, mid);
    t[p].r = build(mid + 1, r);
    return p;
}

int change(int o, int l, int r, int p, int k) {
    int q = ++tot;
    t[q] = t[o];
    if (l == r) {
        t[q].c += k;
        t[q].s += k * b[p];
        return q;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) t[q].l = change(t[o].l, l, mid, p, k);
    else t[q].r = change(t[o].r, mid + 1, r, p, k);
    t[q].c = t[t[q].l].c + t[t[q].r].c;
    t[q].s = t[t[q].l].s + t[t[q].r].s;
    return q;
}

int ask(int p, int l, int r, int k) {
    if (l == r) return t[p].s / t[p].c * k;
    int mid = (l + r) >> 1;
    if (k <= t[t[p].l].c) return ask(t[p].l, l, mid, k);
    else return t[t[p].l].s + ask(t[p].r, mid + 1, r, k - t[t[p].l].c);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int p = (i << 1) - 1, q = i << 1;
        scanf("%d %d %d", &a[p].x, &a[q].x, &a[p].y);
        ++a[q].x;
        a[q].y = -a[p].y;
        b[i] = a[p].y;
    }
    sort(b + 1, b + n + 1);
    int w = unique(b + 1, b + n + 1) - (b + 1);
    rt[0] = build(1, w);
    sort(a + 1, a + (n << 1) + 1);
    int k = 1;
    for (int i = 1; i <= (n << 1); i++) {
        while (k < a[i].x) {
            rt[k+1] = rt[k];
            ++k;
        }
        if (k == n + 1) break;
        int p = lower_bound(b + 1, b + w + 1, abs(a[i].y)) - b;
        rt[k] = change(rt[k], 1, w, p, a[i].y > 0 ? 1 : -1);
    }
    while (m--) {
        int xi, ai, bi, ci;
        scanf("%d %d %d %d", &xi, &ai, &bi, &ci);
        int ki = ((ll)ai * pre + bi) % ci + 1;
        if (t[rt[xi]].c <= ki) printf("%d\n", pre = t[rt[xi]].s);
        else printf("%d\n", pre = ask(rt[xi], 1, w, ki));
    }
    return 0;
}

巴特西

P3168 [CQOI2015]任务查询系统

最新文章

热门文章