题目链接
题解
对于每个时间点建立权值主席树
维护树中前k小的前缀和
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x * f;
}
int m,n;
const int maxn = 300007;
struct Q {
int k,val,tag,sum;
bool operator < (const Q & a) const {
return k < a.k;
}
} s[maxn * 2];
int root[maxn],ls[maxn * 40],rs[maxn * 40],sum[maxn * 40],a[maxn];
int cnt = 0,siz[maxn * 40];
void build(int &x,int l,int r) {
x = ++ cnt;
if(l == r) return;
int mid = l + r >> 1;
build(ls[x],l,mid);
build(rs[x],mid + 1,r);
}
void modify(int &x,int pre,int l,int r,int pos,int tag) {
x = ++ cnt;
sum[x] = sum[pre] + tag * a[pos];
siz[x] = siz[pre] + tag;
ls[x] = ls[pre];
rs[x] = rs[pre];
if(l == r) return;
int mid = l + r >> 1;
if(pos <= mid) modify(ls[x],ls[pre],l,mid,pos,tag);
else modify(rs[x],rs[pre],mid + 1,r,pos,tag);
}
int query(int x,int l,int r,int k) {
if(l == r) return sum[x] / siz[x] * k;
int size = siz[ls[x]];
int mid = l + r >> 1;
if(k <= size) return query(ls[x],l,mid,k);
else return sum[ls[x]] + query(rs[x],mid + 1,r,k - size);
}
main() {
m = read(); n = read();
for(int A,b,c,i = 1;i <= m;++ i) {
A = read(),b = read(),c = read();
s[++ cnt].k = A,s[cnt].val = c;s[cnt].tag = 1;
s[++ cnt].k = b + 1; s[cnt].val = c;s[cnt].tag = -1;
a[i] = c;
}
int num = cnt;cnt = 0;
sort(a + 1,a + m + 1);
sort(s + 1,s + num + 1);
build(root[0],1,n);
for(int i = 1,j = 1;i <= n;++ i) {
root[i] = root[i - 1];
for(;j <= num && s[j].k == i;++ j) {
int pos = lower_bound(a + 1,a + m + 1,s[j].val) - a;
modify(root[i],root[i],1,n,pos,s[j].tag);
}
}
int ans = 1;
for(int t,a,b,c,i = 1;i <= n;++ i) {
t = read(),a = read(),b = read(),c = read();
int K = (a * ans + b) % c + 1;
if(K >= siz[root[t]]) ans = sum[root[t]];
else ans = query(root[t],1,n,K);
printf("%lld
",ans);
}
return 0;
}