题目链接
被自己的sb错误调到自闭。。
主席树的进阶应用。
把\(P_i\)离散化一下，得到每个\(P_i\)的排名，然后建一棵维护\(m\)个位置的主席树，每个结点记录区间总和和正在进行的任务数。
差分一下，主席树维护前缀和，每个时刻一个\(root\)。
然后就是线段树里查前\(k\)小了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 4000010;
struct PT{
int lc, rc, cnt;
long long val;
}t[MAXN << 2];
int rk[MAXN];
struct lsh{
int val, id;
int operator < (const lsh A) const{
return val < A.val;
}
}p[MAXN];
int n, m;
struct Edge{
int next, to, dis;
}e[MAXN];
int head[MAXN], num;
long long pre = 1;
inline void Add(int from, int to, int dis){
e[++num].to = to; e[num].next = head[from]; e[num].dis = dis; head[from] = num;
}
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
int a[MAXN], b[MAXN], c[MAXN], root[MAXN], cnt, r, A, B, C, X, K;
inline void pushup(int x){
t[x].val = t[t[x].lc].val + t[t[x].rc].val;
t[x].cnt = t[t[x].lc].cnt + t[t[x].rc].cnt;
}
int build(int l, int r){
if(l == r) return ++cnt;
int id = ++cnt, mid = (l + r) >> 1;
t[id].lc = build(l, mid);
t[id].rc = build(mid + 1, r);
return id;
}
int update(int q, int l, int r, int x, int y){
if(l == r){ t[++cnt].val = t[q].val + y; t[cnt].cnt = t[q].cnt + (y > 0 ? 1 : -1); return cnt; }
int id = ++cnt, mid = (l + r) >> 1;
t[id] = t[q];
if(x <= mid) t[id].lc = update(t[q].lc, l, mid, x, y);
else t[id].rc = update(t[q].rc, mid + 1, r, x, y);
pushup(id);
return id;
}
long long query(int q, int l, int r, int x){
if(l == r) return t[q].val;
int mid = (l + r) >> 1;
if(t[t[q].lc].cnt >= x) return query(t[q].lc, l, mid, x);
else return t[t[q].lc].val + query(t[q].rc, mid + 1, r, x - t[t[q].lc].cnt);
}
int main(){
m = read(); n = read();
for(int i = 1; i <= m; ++i){
a[i] = read(); r = max(r, b[i] = read());
p[i].id = i; p[i].val = c[i] = read();;
}
sort(p + 1, p + m + 1);
for(int i = 1; i <= m; ++i)
rk[p[i].id] = i;
for(int i = 1; i <= m; ++i){
Add( a[i] , rk[i], c[i]);
Add(b[i] + 1, rk[i], -c[i]);
}
root[0] = build(1, m);
for(int i = 1; i <= n; ++i){
int tmp = root[i - 1];
for(int j = head[i]; j; j = e[j].next)
tmp = update(tmp, 1, m, e[j].to, e[j].dis);
root[i] = tmp;
}
for(int i = 1; i <= n; ++i){
X = read(); A = read(); B = read(); C = read();
K = ((long long)A * pre + B) % C + 1;
printf("%lld\n", pre = query(root[X], 1, m, K));
}
return 0;
}