[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=3932
[算法]
首先 ， 我们可以将(Si , Ei , Pi)转化为在Si处加入Pi ， 在(Ei + 1)出删除Pi
建立可持久化线段树 ， 维护每秒出现任务的个数和优先级的和 ， 即可
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 200010 typedef long long LL; int n , m , idx , version; int S[MAXN] , E[MAXN] , P[MAXN] , root[MAXN * 40] , cnt[MAXN * 40] , tmp[MAXN * 40] , lson[MAXN * 40] , rson[MAXN * 40] , rt[MAXN * 40]; LL sum[MAXN * 40]; multiset< int > ins[MAXN] , del[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void build(int &k , int l , int r) { k = ++idx; cnt[k] = sum[k] = 0; if (l == r) return; int mid = (l + r) >> 1; build(lson[k] , l , mid); build(rson[k] , mid + 1 , r); } inline void modify(int &k , int old , int l , int r , int x , int value) { k = ++idx; lson[k] = lson[old] , rson[k] = rson[old]; cnt[k] = cnt[old] + value; sum[k] = sum[old] + 1LL * tmp[x] * value; if (l == r) return; int mid = (l + r) >> 1; if (mid >= x) modify(lson[k] , lson[k] , l , mid , x , value); else modify(rson[k] , rson[k] , mid + 1 , r , x , value); } inline LL query(int &k , int l , int r , int x) { if (l == r) return 1LL * tmp[l] * min(x , cnt[k]); int mid = (l + r) >> 1; if (cnt[lson[k]] >= x) return query(lson[k] , l , mid , x); else return sum[lson[k]] + query(rson[k] , mid + 1 , r , x - cnt[lson[k]]); } int main() { read(n); read(m); for (int i = 1; i <= n; i++) { read(S[i]); read(E[i]); read(P[i]); tmp[i] = P[i]; } sort(tmp + 1 , tmp + n + 1); int len = unique(tmp + 1 , tmp + n + 1) - tmp - 1; for (int i = 1; i <= n; i++) { P[i] = lower_bound(tmp + 1 , tmp + len + 1 , P[i]) - tmp; ins[S[i]].insert(P[i]); del[E[i] + 1].insert(P[i]); } build(root[version = 0] , 1 , len); for (int i = 1; i <= n; i++) { for (multiset< int > :: iterator it = ins[i].begin(); it != ins[i].end(); it++) { int t = (*it); modify(root[++version] , root[version] , 1 , n , t , 1); } for (multiset< int > :: iterator it = del[i].begin(); it != del[i].end(); it++) { int t = (*it); modify(root[++version] , root[version] , 1 , n , t , -1); } rt[i] = version; } LL pre = 1; for (int i = 1; i <= m; i++) { LL xi , ai , bi , ci; read(xi); read(ai); read(bi); read(ci); int ki = (1LL * ai * (pre % ci) % ci + bi % ci) % ci + 1; printf("%lld " , pre = query(root[rt[xi]] , 1 , n , ki)); } return 0; }