看到这个题有个很暴力的想法，
可以每一个时间点都建一颗主席树，主席树上叶子节点 i 表示优先级为 i 的任务有多少个。
当 x 到 y 有个优先级为 k 的任务时，循环 x 到 y 的每个点，都插入一个 k。
当然这样肯定完蛋。
x 到 y 插入一个优先级为 k 的任务？
想到差分，给时间点为 x 的主席树插入 k，给时间点为 y + 1 的主席树插入 -k。
那么求一个树状数组的前缀和就好了。
前缀和？
用树状数组优化。
这样就可以用 树状数组 套 主席树 来做。
——代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long const int MAXN = 1e5 + , p = ;
int n, m, cnt, t;
int S[MAXN], E[MAXN], P[MAXN], num[MAXN], root[MAXN], id[MAXN], q[], s[MAXN * p], ls[MAXN * p], rs[MAXN * p];
LL sum[MAXN * p], pre = ; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline bool cmp(int x, int y)
{
return P[x] < P[y];
} inline void insert(int last, int &now, int l, int r, int x, int v1, int v2)
{
if(!now) now = ++cnt;
sum[now] = sum[last] + v1, s[now] = s[last] + v2, ls[now] = ls[last], rs[now] = rs[last];
if(l == r) return;
int mid = (l + r) >> ;
if(x <= mid) insert(ls[last], ls[now], l, mid, x, v1, v2);
else insert(rs[last], rs[now], mid + , r, x, v1, v2);
} inline LL query(int l, int r, int k)
{
if(l == r)
{
LL t2 = ;
for(int i = ; i <= t; i++) t2 += sum[q[i]];
return t2;
}
LL t2 = ;
int t1 = , mid = (l + r) >> ;
for(int i = ; i <= t; i++) t1 += s[ls[q[i]]], t2 += sum[ls[q[i]]];
if(k <= t1)
{
for(int i = ; i <= t; i++) q[i] = ls[q[i]];
return query(l, mid, k);
}
else
{
for(int i = ; i <= t; i++) q[i] = rs[q[i]];
return t2 + query(mid + , r, k - t1);
}
} int main()
{
int i, j, x, a, b, c;
LL k;
n = read();
m = read();
for(i = ; i <= n; i++)
{
S[i] = read();
E[i] = read();
P[i] = read();
id[i] = i;
}
std::sort(id + , id + n + , cmp);
for(i = ; i <= n; i++) num[id[i]] = i;
for(i = ; i <= n; i++)
{
for(j = S[i]; j <= n; j += j & -j) insert(root[j], root[j], , n, num[i], P[i], );
for(j = E[i] + ; j <= n; j += j & -j) insert(root[j], root[j], , n, num[i], -P[i], -);
}
for(i = ; i <= m; i++)
{
scanf("%d %d %d %d", &x, &a, &b, &c);
k = + (LL)(a * pre + b) % c;
t = ;
for(j = x; j; j -= j & -j) q[++t] = root[j];
pre = query(, n, k);
printf("%lld\n", pre);
}
return ;
}
其实如果按照时间排序的话，依次插入主席树，就可以维护前缀和，而省去了树状数组的麻烦。
然后注意的是每个时间点有可能会有多颗主席树。
——代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long const int MAXN = 1e5 + ;
int n, m, tot, size, cnt;
int num[MAXN], id[MAXN], v[MAXN], ls[MAXN * ], rs[MAXN * ], s[MAXN * ], root[MAXN];
LL pre = , sum[MAXN * ];
struct node
{
int S, val, type, num;
}p[MAXN * ]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline bool cmp(node x, node y)
{
return x.S < y.S;
} inline void insert(int &now, int l, int r, int x, int v1, int v2)
{
++cnt;
sum[cnt] = sum[now] + v1;
s[cnt] = s[now] + v2;
ls[cnt] = ls[now];
rs[cnt] = rs[now];
now = cnt;
if(l == r) return;
int mid = (l + r) >> ;
if(x <= mid) insert(ls[now], l, mid, x, v1, v2);
else insert(rs[now], mid + , r, x, v1, v2);
} inline LL query(int now, int l, int r, int x)
{
if(l == r) return sum[now];
int mid = (l + r) >> ;
if(x <= s[ls[now]]) return query(ls[now], l, mid, x);
else return sum[ls[now]] + query(rs[now], mid + , r, x - s[ls[now]]);
} inline bool cmp1(int x, int y)
{
return v[x] < v[y];
} int main()
{
int i, j, x, y, z, a;
LL k;
n = read();
m = read();
for(i = ; i <= n; i++)
{
x = read();
y = read();
v[i] = read();
num[i] = i;
p[++tot].S = x, p[tot].val = v[i], p[tot].type = ;
p[++tot].S = y + , p[tot].val = -v[i], p[tot].type = -;
}
std::sort(num + , num + n + , cmp1);
for(i = ; i <= n; i++) id[num[i]] = i;
/*std::sort(v + 1, v + n + 1);
size = std::unique(v + 1, v + n + 1) - (v + 1);
for(i = 1; i <= n; i++) id[i] = std::lower_bound(v + 1, v + size + 1, id[i]) - v;*/
tot = ;
for(i = ; i <= n; i++) p[++tot].num = id[i], p[++tot].num = id[i];
std::sort(p + , p + tot + , cmp);
j = ;
for(i = ; i <= m; i++)
{
root[i] = root[i - ];
while(p[j].S == i)
insert(root[i], , n, p[j].num, p[j].val, p[j].type), j++;
}
for(i = ; i <= m; i++)
{
a = read();
x = read();
y = read();
z = read();
k = + (LL)(x * pre + y) % z;
printf("%lld\n", pre = query(root[a], , n, k));
}
return ;
}
最后，需要注意对动态开点的理解。
以及，这个题是对优先级离散化，优先级有可能有相同的，但是离散化却不去重，这就会使得相同数值会是递增的一段数。
为什么不去重？
这是为了方便找前 k 个。
如果去重，有可能 query 时，找到一个叶子节点它的个数会超过一个，比如说 5 个，而只要找 3 个，那样处理就比较麻烦，还得再记录每个叶子节点的优先级。
不去重就保证了每个叶节点的个数只有一个，而对于答案没有影响。