题目描述
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。
输入格式
输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，对于第一次查询，Pre=1。
输出格式
输出共n行，每行一个整数，表示查询结果。
#include#define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;typedef long long ll;template inline void rd(T&x){ char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x;}const int maxn=1e5+5;int n,m,tot,a[maxn],ls[maxn*100],rs[maxn*100],cnt[maxn*100],T[maxn];ll sum[maxn*100];//你可以按照时间顺序一个一个往里面放//也可以用一种类似于启发式合并的方式,先建树后合并 struct node{ int start,end,priority;}task[maxn];inline void pushup(int rt){ sum[rt]=sum[ls[rt]]+sum[rs[rt]]; cnt[rt]=cnt[ls[rt]]+cnt[rs[rt]];}inline void add(int &rt,int l,int r,int pos,int num){ if(!rt)rt=++tot; if(l==r) { sum[rt]+=1ll*num*a[l]; cnt[rt]+=num; re ; } int mid=(l+r)>>1; if(pos<=mid)add(ls[rt],l,mid,pos,num); else add(rs[rt],mid+1,r,pos,num); pushup(rt);}inline int merge(int x,int y){ if(!x||(!y))re x+y; int rt=++tot; sum[rt]=sum[x]+sum[y]; cnt[rt]=cnt[x]+cnt[y]; ls[rt]=merge(ls[x],ls[y]); rs[rt]=merge(rs[x],rs[y]); re rt; }inline ll query(int rt,int l,int r,int k){ if(l==r)re 1ll*a[l]*min(k,cnt[rt]); int mid=(l+r)>>1; if(cnt[ls[rt]]>=k)re query(ls[rt],l,mid,k); else re sum[ls[rt]]+query(rs[rt],mid+1,r,k-cnt[ls[rt]]);}int main(){// freopen("in.txt","r",stdin); ll x,u,v,w,k; rd(n);rd(m); inc(i,1,n) { rd(task[i].start),rd(task[i].end),rd(task[i].priority); a[i]=task[i].priority; } sort(a+1,a+n+1); int N=unique(a+1,a+n+1)-(a+1); //主席树日常操作李三花 inc(i,1,n) { int pos=lower_bound(a+1,a+N+1,task[i].priority)-a; add(T[task[i].start],1,N,pos,1); add(T[task[i].end+1],1,N,pos,-1); } inc(i,1,m+1) T[i]=merge(T[i-1],T[i]); ll pre=1; inc(i,1,m) { rd(x),rd(u),rd(v),rd(w); k=1+(u*pre%w+v)%w; pre=query(T[x],1,N,k); printf("%lld\n",pre); } re 0;}