题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3932
BZOJ：Time Limit: 20 Sec Memory Limit: 512 MB
洛谷：
时间限制2.00s
内存限制500.00MB
Description
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的
任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行
），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向
查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个
）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先
级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。
Input
输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格
分开的正整数Si、Ei和Pi(Si≤Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，
描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，
对于第一次查询，Pre=1。
Output
输出共n行，每行一个整数，表示查询结果。
Sample Input
4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
Sample Output
2
8
11
8
11
HINT
样例解释
K1 = (1*1+3)%2+1 = 1
K2 = (1*2+3)%4+1 = 2
K3 = (2*8+4)%3+1 = 3
对于100%的数据，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi为1到n的一个排列
中文题面，很友好，另外洛谷的K值公式打错了。。。
题面求的是对于单个时间的前k小值之和，那么前k小值之和的话很容易想到主席树。但是怎么维护是一个问题。如果直接暴力化成单点修改的话不仅时间上无法承受，空间上也是无法承受的。所以巨巨们就想到了差分。。。每次的区间修改只需要修改头尾两端，即update(st),update(ed+1);相信各位学主席树的时候一定学过了树状数组。。。那么差分也肯定学过，就不多说了。
首先我们对每一个时刻建树，那么查询的时候我们直接在第x个树中找就行了。在每一个时刻上，有区间开始或者结束，那么我们就是直接更新在此时刻的开始和结束用1和-1表示其数量，1|-1*b[pos]作为其优先级，那么这就是一个差分了，其中b[pos]是该优先级的离散化后的大小：
for (int i=1; i<=m; i++) { for (int j=0; j<st[i].size(); j++) { int p=lower_bound(fall+1,fall+1+nb,lis[st[i][j]])-fall; ver[++np]=update(1,nb,p,1,ver[np-1]); } for (int j=0; j<ed[i].size(); j++) { int p=lower_bound(fall+1,fall+1+nb,lis[ed[i][j]])-fall; ver[++np]=update(1,nb,p,-1,ver[np-1]); } last[i]=ver[np]; }
不过和之前有所区别的是这里的版本每次会产生0到2个，而不是唯一的一个，所以我们第i个时刻所产生的的最终的版本应该另外记录一下，这里我用的是last记录的
update函数和query函数的话就不多讲了，上一篇主席树的区间前k大值都有涉及到，最后再提醒一下，每个点可能有很多数量，所以query的l==r的时候应该用sum/num*k，其中k是剩余的数量，相当于单价*数量。。。
以下是AC代码：（洛谷A不了，详情请看我的博客说明）
#include <bits/stdc++.h> using namespace std; #define ll long long const int mac=1e5+10; struct Tree { ll sum; int size,l,r; }tree[mac<<6]; int lis[mac],fall[mac],ver[mac*2]; vector<int>st[mac],ed[mac]; int last[mac]; int tot=0; void in(int &x) { int f=0; char ch=getchar(); while (ch>'9' || ch<'0') ch=getchar(); while (ch>='0' && ch<='9') f=(f<<1)+(f<<3)+ch-'0',ch=getchar(); x=f; } int build(int l,int r) { int mid=(l+r)>>1; int rt=++tot; if (l==r) return rt; tree[rt].l=build(l,mid); tree[rt].r=build(mid+1,r); return rt; } int update(int l,int r,int pos,int val,int per) { int rt=++tot; tree[rt]=tree[per]; tree[rt].size+=val;tree[rt].sum+=1ll*val*fall[pos]; if (l==r) return rt; int mid=(l+r)>>1; if (mid>=pos) tree[rt].l=update(l,mid,pos,val,tree[per].l); else tree[rt].r=update(mid+1,r,pos,val,tree[per].r); return rt; } ll query(int l,int r,int rt,int k) { int x=tree[tree[rt].l].size; if (l==r) return tree[rt].sum/(1ll*tree[rt].size)*1ll*k; int mid=(l+r)>>1; if (x>=k) return query(l,mid,tree[rt].l,k); else return query(mid+1,r,tree[rt].r,k-x)+tree[tree[rt].l].sum; } int main() { int n,m; in(n);in(m); for (int i=1; i<=n; i++){ int x,y,z; in(x);in(y);in(z); lis[i]=z;fall[i]=z; st[x].push_back(i); ed[y+1].push_back(i); } sort(fall+1,fall+1+n); int nb=unique(fall+1,fall+1+n)-fall-1; ver[0]=build(1,nb); int np=0; for (int i=1; i<=m; i++){ for (int j=0; j<st[i].size(); j++){ int p=lower_bound(fall+1,fall+1+nb,lis[st[i][j]])-fall; ver[++np]=update(1,nb,p,1,ver[np-1]); } for (int j=0; j<ed[i].size(); j++){ int p=lower_bound(fall+1,fall+1+nb,lis[ed[i][j]])-fall; ver[++np]=update(1,nb,p,-1,ver[np-1]); } last[i]=ver[np]; } ll per=1; for (int i=1; i<=m; i++){ int x,a,b,c; in(x);in(a);in(b);in(c); ll k=(1ll*a*per+b)%c+1; if (tree[last[x]].size<=k) per=tree[last[x]].sum; else per=query(1,nb,last[x],k); printf ("%lld ",per); } return 0; }