主席树。
把区间的影响挂在左端点与右端点，建树时顺便对应的插入与删除。
维护一段值域区间的和与数字个数，查询时要注意与第k大的数相同的数可能有很多。
复杂度O(nlogn)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<cmath> #include<stack> #include<map> #define P puts("lala") #define cp cerr<<"lala"<<endl #define ln putchar(' ') #define sp putchar(' ') #define pb push_back #define pf push_front #define fi first #define se second #define mkp make_pair using namespace std; typedef pair<int,int> pii; inline void read(int &re) { char ch=getchar();int g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar(); re*=g; } typedef long long ll; inline void read(ll &re) { char ch=getchar();ll g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar(); re*=g; } const int N=100050; int p[N],b[N],to[N],n,m,L[N],R[N],tot,rt[N],ch[N*45][2],cnt[N*45],sz; ll sum[N*45]; vector<int>ve1[N],ve2[N]; void build(int &o,int l,int r) { o=++sz; sum[o]=cnt[o]=0; if(l==r) return ; int mid=l+r>>1; build(ch[o][0],l,mid);build(ch[o][1],mid+1,r); } void update(int &o,int last,int l,int r,int x,int k) //k*x { if(o==last) { o=++sz; ch[o][0]=ch[last][0];ch[o][1]=ch[last][1]; cnt[o]=cnt[last]+k;sum[o]=sum[last]+k*b[x]; } else { cnt[o]+=k;sum[o]+=k*b[x]; } if(l==r) return ; int mid=l+r>>1; if(x<=mid) update(ch[o][0],ch[last][0],l,mid,x,k); else update(ch[o][1],ch[last][1],mid+1,r,x,k); } ll query(int o,int l,int r,int k) { if(l==r) {return b[l]*k;} int mid=l+r>>1; ll ans=0; if(k<=cnt[ch[o][0]]) return query(ch[o][0],l,mid,k); else return query(ch[o][1],mid+1,r,k-cnt[ch[o][0]])+sum[ch[o][0]]; } int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin);freopen("1.out","w",stdout); #endif int i,j,opt,T; read(m);read(n); for(i=1;i<=m;++i) { read(L[i]);read(R[i]);read(p[i]);b[i]=p[i]; } sort(b+1,b+1+m); tot=unique(b+1,b+1+m)-(b+1); for(i=1;i<=m;++i) to[i]=lower_bound(b+1,b+1+tot,p[i])-b; build(rt[0],1,tot); for(i=1;i<=m;++i) ve1[L[i]].pb(to[i]),ve2[R[i]+1].pb(to[i]); for(i=1;i<=n;++i) { int siz=ve1[i].size(); rt[i]=rt[i-1]; for(j=0;j<siz;++j) update(rt[i],rt[i-1],1,tot,ve1[i][j],1); siz=ve2[i].size(); for(j=0;j<siz;++j) update(rt[i],rt[i-1],1,tot,ve2[i][j],-1); } ll pre=1; for(int cas=1;cas<=n;++cas) { int x,a,b,c,k; read(x);read(a);read(b);read(c); k=1+(a*pre+b)%c; if(k>cnt[rt[x]]) k=cnt[rt[x]]; pre=query(rt[x],1,tot,k); printf("%lld ",pre); } return 0; } /* */