题目链接：戳我
主席树维护K大，考虑到利用主席树前缀和的性质。把每个任务拆分成权值为1的进入操作，和权值为-1的退出操作（注意因为是闭区间，所以右边的位置加进去的时候需要+1）
（应该是个动态开点的权值线段树一样的东西吧）维护v，表示该节点维护的任务数量是多少。sum表示该节点维护的任务总和是多少。输出k大的时候（因为有可能存在该节点有很多一样的值的情况）直接用总和除以数量即可。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 120010
using namespace std;
int n,m,cnt,tot,sum;
int rt[MAXN],cur[MAXN];
long long pre=1;
struct Node{int pos,w,p;}node[MAXN<<1];
struct Node2{int ls,rs,v;long long sum;}t[MAXN<<5];
inline bool cmp(struct Node x,struct Node y){return x.pos<y.pos;}
void modify(int &now,int ff,int l,int r,int pos,int w)
{
now=++tot;
t[now]=t[ff];t[now].v+=w;t[now].sum+=cur[pos]*w;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid) modify(t[now].ls,t[ff].ls,l,mid,pos,w);
else modify(t[now].rs,t[ff].rs,mid+1,r,pos,w);
}
long long query(int now,int l,int r,int k)
{
if(t[now].v<=k)return t[now].sum;
if(l==r)return t[now].sum/(1ll*t[now].v)*1ll*k;
int mid=(l+r)>>1;
if(k<=t[t[now].ls].v)return query(t[now].ls,l,mid,k);
else return t[t[now].ls].sum+query(t[now].rs,mid+1,r,k-t[t[now].ls].v);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int s,t,p;
scanf("%d%d%d",&s,&t,&p);
node[++cnt].pos=s,node[cnt].w=1,node[cnt].p=p;
node[++cnt].pos=t+1,node[cnt].w=-1,node[cnt].p=p;
cur[++sum]=node[cnt].p;
}
sort(&cur[1],&cur[sum+1]);
sum=unique(&cur[1],&cur[1+sum])-cur-1;
sort(&node[1],&node[1+cnt],cmp);
for(int i=1;i<=cnt;i++)
node[i].p=lower_bound(&cur[1],&cur[1+sum],node[i].p)-cur;
for(int i=1;i<=cnt;i++)
modify(rt[node[i].pos],rt[node[i-1].pos],1,sum,node[i].p,node[i].w);
for(int i=1;i<=m;i++)
if(!rt[i])
rt[i]=rt[i-1];
while(n--)
{
int x,a,b,c,k;
scanf("%d%d%d%d",&x,&a,&b,&c);
k=1+(1ll*a*pre+b)%c;
printf("%lld
",pre=query(rt[x],1,sum,k));
}
return 0;
}