题面
题目传送门
解法
可以用可持久化线段树来实现一些离线且使用线段树的问题
- 对于一个任务 (l,r,x) ( l , r , x ) ,就可以等同于在 [l,r] [ l , r ] 这段区间中全部插入一个数 x x
- 暴力做这个事情显然是不可取的
- 我们可以考虑将这个区间加法变成差分,即在ll这个位置插入一个数 x x ,在r+1r+1这个位置把 x x 删除,然后做一遍前缀和即为这个位置具体有什么数
- 能处理前缀和的数据结构似乎也只有主席树了
- 直接用主席树来实现这个过程即可
- 最后查询的时候只要在询问的那一个树上跑就可以了
- 时间复杂度:O(nloga[i]+mloga[i])O(nloga[i]+mloga[i])
【注意事项】
- 如果存在修改,那么一定要重新开一棵树
- 因为数可能会出现重复的情况,所以我们在走到叶节点的时候要取一个 min m i n
代码
#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
template <typename node> void chkmax(node &x, node y) {x = max(x, y);}
template <typename node> void chkmin(node &x, node y) {x = min(x, y);}
template <typename node> void read(node &x) {
x = ; int f = ; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -; c = getchar();}
while (isdigit(c)) x = x * + c - '0', c = getchar(); x *= f;
}
struct Node {
int lc, rc, cnt, sum;
} t[N * ];
struct Info {
int x, v;
};
int tot, rt[N * ], num[N];
vector <Info> v[N];
int ins(int k, int l, int r, int x, int v) {
int ret = ++tot; t[ret] = t[k];
t[ret].cnt += v, t[ret].sum += v * x;
if (l == r) return ret; int mid = (l + r) >> ;
if (x <= mid) t[ret].lc = ins(t[k].lc, l, mid, x, v);
else t[ret].rc = ins(t[k].rc, mid + , r, x, v);
return ret;
}
int query(int k, int l, int r, int x) {
if (!k) return ;
if (l == r) return l * min(t[k].cnt, x);
int mid = (l + r) >> , tmp = t[t[k].lc].cnt;
if (x <= tmp) return query(t[k].lc, l, mid, x);
return t[t[k].lc].sum + query(t[k].rc, mid + , r, x - tmp);
}
main() {
int n, q; read(n), read(q);
for (int i = ; i <= n; i++) {
int l, r, x; read(l), read(r), read(x);
v[l].push_back((Info) {x, });
v[r + ].push_back((Info) {x, -});
}
int len = ;
for (int i = ; i <= q; i++) {
num[i] = ++len; rt[len] = rt[len - ];
for (int j = ; j < v[i].size(); j++) {
Info tmp = v[i][j];
int x = tmp.x, v = tmp.v;
num[i] = ++len;
rt[len] = ins(rt[len - ], , , x, v);
}
}
int las = ;
while (q--) {
int x, a, b, c, k;
read(x), read(a), read(b), read(c);
k = + (a * las % c + b) % c;
las = query(rt[num[x]], , , k);
cout << las << "\n";
}
return ;
}