妈的我的主席树怎么这么垃圾。
好的这绝对是主席树，维护区间第k小。
好的看上去怎么在线搞？
我们建图的时候考虑差分。
start 1->end+1 -1；
好的建一棵主席树。
但是这里是要离散化的。
于是坑点来了：你在维护区间第k小前缀和的时候，你使用的fix是p的离散化吧，但是你维护前缀不能用这个离散过后的p对吧。
再观察题目：它们的优先级可能相同，也可能不同
这就告诉我们需要维护一个siz。
但是维护区间第k小时siz用不完啊，你不能return sum 啊。
于是这里考虑一个sum/siz*k
然后还有。
你用时间建树，这并不能保证时间是连续的，于是你得排序时间后跑一个循环把树的版本连上。
然后注意有pre强制在线哦
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; inline void read(int &x){ x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f; } const int N=1e6*5+100; const int maxn=2e5+10; int root[N]={0}; int sum[N]={0}; int lson[N]={0}; int rson[N]={0}; int siz[N]={0}; int cnt=0; int hash[N]={0}; void update(int l,int r,int x,int &y,int val,int delta){ // if(!y){ cnt++; y=cnt; lson[y]=lson[x]; rson[y]=rson[x]; // } // cout<<y<<" "<<delta<<" "<<val<<endl; sum[y]=sum[x]+hash[val]*delta; siz[y]=siz[x]+delta; if(l==r){ return; } int mid=(l+r)/2; if(val<=mid){ update(l,mid,lson[x],lson[y],val,delta); } else{ update(mid+1,r,rson[x],rson[y],val,delta); } } int quary(int l,int r,int rt,int k){ int t=siz[rt]; // cout<<t<<" "<<l<<" "<<r<<endl; if(k>=t){ return sum[rt]; } if(l==r){ return (sum[rt]/siz[rt])*k; } t=siz[lson[rt]]; // cout<<"tnow== "<<t<<" "<<lson[rt]<<" "<<rson[rt]<<endl; int mid=(l+r)/2; int ans=0; if(t>=k){ ans+=quary(l,mid,lson[rt],k); } else{ ans+=sum[lson[rt]]+quary(mid+1,r,rson[rt],k-t); } // cout<<"ans= "<<ans<<endl; return ans; } int n,m; struct Data{ int time,fix,sum; }a[maxn]; bool cmp(Data a,Data b){ return a.time<b.time; } int main(){ read(m); read(n); // scanf("%d%d",&m,&n); for(int i=1;i<=m;i++){ int s,e,p; read(s); read(e); read(p); // scanf("%d%d%d",&s,&e,&p); a[i*2-1]=(Data){s,p,1}; a[i*2]=(Data){e+1,p,-1}; hash[i]=p; } sort(hash+1,hash+1+m); int len=unique(hash+1,hash+1+m)-hash-1; sort(a+1,a+1+2*m,cmp); // cout<<len<<endl; for(int i=1;i<=m*2;i++){ // cout<<"time "<<a[i].time<<endl; int x=lower_bound(hash+1,hash+1+len,a[i].fix)-hash; // cout<<x<<endl; int t=a[i].time; if(i==1||a[i-1].time!=a[i].time){ if(i!=1){ for(int j=a[i-1].time+1;j<t;j++){ // cout<<"working"<<endl; root[j]=root[j-1]; // update(1,len,root[j-1],root[j],1,0); } } update(1,len,root[t-1],root[t],x,a[i].sum); } else{ update(1,len,root[t],root[t],x,a[i].sum); } } /*for(int i=1;i<=cnt;i++){ cout<<siz[i]<<" "; } cout<<endl;*/ /*cout<<root[3]<<endl;*/ int pre=1; for(int i=1;i<=n;i++){ int x,a,b,c; read(x); read(a); read(b); read(c); // scanf("%d%d%d%d",&x,&a,&b,&c); pre=(a*pre+b)%c+1; // cout<<"pre=="<<pre<<endl; printf("%d\n",pre=quary(1,len,root[x],pre)); } }