几乎是一个可持久化线段树板子，但是调了半天，因为有一个坑点。此题要维护一个加点，删点的线段树，查找前$k$小的和，所以可以想到差分维护删除。先将优先级离散化，然后每次通过时间建树，内容存的是优先级，然后就慢慢去写就行，最后发现有一步是if(l==r) return sum[rt]/size[rt]*tot,里面$sum[i]$表示当前以i为节点的优先级之和,$size[i]$表示里面还有几个任务，因为有可能都选会超过所要求的，所以要除以下，并且那个坑点是$size[rt]$有可能为$0$，所以就炸了，就这个坑调了半天
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=100050; struct node{ int pos,tag,val,valv; }x[MAXN<<1]; int cnt,ls[MAXN<<7],rs[MAXN<<7],tr[MAXN<<7],n,m,pos; ll sum[MAXN<<7]; int size[MAXN<<7],val[MAXN]; bool cmp(node x1,node x2){ return x1.pos<x2.pos; } int st; void build(int &rt,int l,int r){ rt=++st; if(l==r) return; int mid=l+r>>1; build(ls[rt],l,mid),build(rs[rt],mid+1,r); return; } void update(int &rt,int las,int l,int r,int xx,int tag){ rt=++st;ls[rt]=ls[las],rs[rt]=rs[las],sum[rt]=sum[las],size[rt]=size[las]; sum[rt]+=tag*(ll)val[xx],size[rt]+=tag; if(l==r) return; int mid=l+r>>1; if(xx<=mid) update(ls[rt],ls[las],l,mid,xx,tag); else update(rs[rt],rs[las],mid+1,r,xx,tag); return; } int query(int rt,int l,int r,int tot){ if(tot>=size[rt]) return sum[rt]; if(l==r) return sum[rt]/size[rt]*tot; int mid=l+r>>1,siz=size[ls[rt]];ll res=0; if(tot<=siz) res+=query(ls[rt],l,mid,tot); else res+=sum[ls[rt]]+query(rs[rt],mid+1,r,tot-siz); return res; } ll pre=1; signed main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ x[++cnt].pos=read(),x[cnt].tag=1; x[++cnt].pos=read()+1,x[cnt].tag=-1,x[cnt].val=x[cnt-1].val=val[i]=read(); } sort(val+1,val+n+1); sort(x+1,x+cnt+1,cmp); int d=unique(val+1,val+n+1)-(val+1); for(int i=1;i<=cnt;i++) x[i].valv=lower_bound(val+1,val+n+1,x[i].val)-val; build(tr[0],1,d); pos=1; for(int i=1;i<=m;i++){ tr[i]=tr[i-1]; while(x[pos].pos==i){ update(tr[i],tr[i],1,d,x[pos].valv,x[pos].tag);pos++; } } for(int i=1;i<=m;i++){ int time=read(),a=read(),b=read(),c=read(); int k=1+(a*pre+b)%c; if(sum[tr[time]]<=k) printf("%lld ",pre=sum[tr[time]]); else printf("%lld ",pre=query(tr[time],1,d,k)); } }