P3168 [CQOI2015]任务查询系统

xht

2019-02-25 16:31:41

Solution

题目地址:[P3168 [CQOI2015]任务查询系统](https://www.luogu.org/problemnew/show/P3168) 主席树的模板题 更模板的在这儿:[P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.org/problemnew/show/P3834) 形象的说,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; } ```