模板题...
差分，然后用主席树维护时间点上的优先值和就好了
就是细节烦...
1 #include<bits/stdc++.h> 2 #define int long long 3 #define mid (l+r>>1) 4 #define writeln(x) write(x),puts("") 5 #define writep(x) write(x),putchar(' ') 6 using namespace std; 7 inline int read(){ 8 int ans=0,f=1;char chr=getchar(); 9 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 10 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 11 return ans*f; 12 }void write(int x){ 13 if(x<0) putchar('-'),x=-x; 14 if(x>9) write(x/10); 15 putchar(x%10+'0'); 16 }const int M = 2e5+5; 17 int rt[M*20],s[M*20],ls[M*20],rs[M*20],cnt[M*20],n,m,lst,x,y,k,a[M],b[M],T; 18 vector<int> aa[M],bb[M]; 19 void Update(int &x,int y,int l,int r,int p,int opt){ 20 x=++T;ls[x]=ls[y],rs[x]=rs[y],s[x]=s[y]+opt*b[p],cnt[x]=cnt[y]+opt; 21 if(l==r) return; 22 if(p<=mid) Update(ls[x],ls[x],l,mid,p,opt); 23 else Update(rs[x],rs[x],mid+1,r,p,opt); 24 } 25 int Query(int x,int l,int r,int k){ 26 if(l==r) return s[x]/cnt[x]*k; 27 int t=cnt[ls[x]]; 28 if(k<=t) return Query(ls[x],l,mid,k); 29 return Query(rs[x],mid+1,r,k-t)+s[ls[x]]; 30 } 31 signed main(){ 32 n=read(),m=read(); 33 for(int i=1,x,y,z;i<=n;i++){ 34 x=read(),y=read();a[i]=b[i]=read(); 35 aa[x].push_back(i),bb[y+1].push_back(i); 36 }sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1; 37 for(int i=1,pos;i<=m;i++){ 38 rt[i]=rt[i-1]; 39 for(int j=0;j<aa[i].size();j++){ 40 pos=lower_bound(b+1,b+len+1,a[aa[i][j]])-b; 41 Update(rt[i],rt[i],1,len,pos,1); 42 } 43 for(int j=0;j<bb[i].size();j++){ 44 pos=lower_bound(b+1,b+len+1,a[bb[i][j]])-b; 45 Update(rt[i],rt[i],1,len,pos,-1); 46 } 47 }lst=1; 48 while(m--){ 49 int x=read(),y=read(),z=read(),w=read(); 50 k=(lst*y+z)%w+1; 51 if(k>cnt[rt[x]]) writeln(lst=s[rt[x]]); 52 else writeln(lst=Query(rt[x],1,len,k)); 53 }return 0; 54 }
然而悲伤的是：洛谷上暴力跑的最快惹qaq，排行榜第一页全是暴力,转行打暴力吧
upd:经测试bzoj上暴力跑得也贼快，上了第一页
贴一下暴力代码：
#include<bits/stdc++.h> #define re register int using namespace std; inline int read(){ int ans=0,f=1;char chr=getchar(); while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} return ans*f; }const int N=1e5+10; struct P{int s,e,p;}a[N]; int n,m,sum;long long ans=1; inline bool cmp(const P&a,const P&b){return a.p<b.p;} int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i].s=read(),a[i].e=read(),a[i].p=read(); sort(a+1,a+n+1,cmp);re x,q,w,e,k; while(m--){ x=read(),q=read(),w=read(),e=read(); k=(1ll*q*ans%e+w)%e+1;ans=sum=0; for(re i=1;i<=n&&sum<k;++i) if(a[i].s<=x&&x<=a[i].e)ans+=a[i].p,++sum; printf("%lld ",ans); }return 0; }