这是一道好题 可以更深的理解主席树
最初的想法是 一开始 一边加入任务 一边维护时间轴
换句话说 对于每个时间点 我们都想维护一颗权值线段树（这里的权值代表着优先级Pi）相当于对于一个任务 我们要维护Ei-Si棵
然而显然MLE 考虑降维
联想到主席树建树方式是通过前缀和来的
既然是求前缀和 这道题的每个任务相当于区间修改 会不会与差分数组有关呢？
答案是正确的
所以一开始我们想维护的Ei-Si棵权值线段树 变成只维护Ei,Si+1这两棵就行了 Ei进行+1，Si+1进行-1
因此我们按顺序 rebuild这些权值线段树 把他们合并成主席树
然后就可以query了
#include<bits/stdc++.h> #define int long long #define N 100005 using namespace std; int m,n,a[N],num,rt[N*100],tot,lson[N*100],rson[N*100],cnt[N*100],sum[N*100]; struct Task { int from,to,val; }task[N]; inline void pushup(int now) { sum[now]=sum[lson[now]]+sum[rson[now]]; cnt[now]=cnt[lson[now]]+cnt[rson[now]]; } inline void build(int &now,int l,int r,int pos,int del) { if(!now) now=++tot; if(l==r) { cnt[now]+=del; sum[now]=cnt[now]*a[l]; return; } int m=(l+r)>>1; if(pos<=m) build(lson[now],l,m,pos,del); else build(rson[now],m+1,r,pos,del); pushup(now); } inline int rebuild(int x,int y) { if(!x||!y) return x+y; int now=++tot; sum[now]=sum[x]+sum[y]; cnt[now]=cnt[x]+cnt[y]; lson[now]=rebuild(lson[x],lson[y]); rson[now]=rebuild(rson[x],rson[y]); return now; } inline int query(int now,int l,int r,int k) { if(l==r) return a[l]*min(k,cnt[now]); int m=(l+r)>>1; if(cnt[lson[now]]>=k) return query(lson[now],l,m,k); else return sum[lson[now]]+query(rson[now],m+1,r,k-cnt[lson[now]]); } main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>m>>n; for(int i=1;i<=m;i++) { cin>>task[i].from>>task[i].to>>task[i].val; a[i]=task[i].val; } sort(a+1,a+1+m); ++n; num=unique(a+1,a+1+m)-a-1; for(int i=1;i<=m;i++) { task[i].val=lower_bound(a+1,a+1+num,task[i].val)-a; build(rt[task[i].from],1,num,task[i].val,1); build(rt[task[i].to+1],1,num,task[i].val,-1); } for(int i=1;i<=n;i++) { rt[i]=rebuild(rt[i-1],rt[i]); } int pre=1; for(int i=1;i<n;i++) { int x,a,b,c,k; cin>>x>>a>>b>>c; k=1+(a*pre+b)%c; pre=query(rt[x],1,num,k); cout<<pre<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9801112.html
