最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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行，每行一个整数，表示查询结果。
在教师听着课，写了一上午没有过，回到宿舍听着歌，就A了。神奇
#include<bits/stdc++.h> using namespace std; #define ll long long const int M=210000; struct Node{int ls,rs,num;ll v;}t[M*40];//主席树 struct node{int l,r,v;}d[M]; int n,m,b[M],cnt,rot[M]; vector<int> G[M]; void build(int &k,int l,int r){ k=++cnt; t[k].num=t[k].v=t[k].ls=t[k].rs=0; if(l==r)return; int mid=l+r>>1; build(t[k].ls,l,mid); build(t[k].rs,mid+1,r); } void update(int pre,int &k,int l,int r,int in,int type){ k=++cnt;t[k]=t[pre]; t[k].num+=type;t[k].v+=b[in]*type; if(l==r)return ; int mid=(l+r)>>1; if(in<=mid)update(t[pre].ls,t[k].ls,l,mid,in,type); else update(t[pre].rs,t[k].rs,mid+1,r,in,type); } ll ask(int k,int num,int l,int r){ if(t[k].num<=num)return t[k].v; if(l==r) return num*b[l]; int mid=(l+r)>>1; if(t[t[k].ls].num>=num)return ask(t[k].ls,num,l,mid); return ask(t[k].rs,num-t[t[k].ls].num,mid+1,r)+t[t[k].ls].v; } int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].v),b[i]=d[i].v; sort(b+1,b+m+1); int tott=1; for(int i=2;i<=m;i++)if(b[i]!=b[i-1])b[++tott]=b[i];b[0]=tott; for(int i=1;i<=m;i++) { d[i].v=lower_bound(b+1,b+b[0]+1,d[i].v)-b; G[d[i].l].push_back(d[i].v); G[d[i].r+1].push_back(-d[i].v); } build(rot[0],1,b[0]); for(int i=1;i<=n;i++){ if(G[i].size()==0){ rot[i]=rot[i-1]; continue; } update(rot[i-1],rot[i],1,b[0],abs(G[i][0]),G[i][0]<0?-1:1); for(int j=1;j<G[i].size();j++)update(rot[i],rot[i],1,b[0],abs(G[i][j]),G[i][j]<0?-1:1); } ll pre=1,a,b1,c,x,k; for(int i=1;i<=n;i++){ scanf("%lld%lld%lld%lld",&x,&a,&b1,&c); k=1+(a*pre+b1)%c; pre=ask(rot[x],k,1,b[0]); printf("%lld\n",pre); } return 0; }
