题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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行，每行一个整数，表示查询结果。

 

输入输出样例

输入样例#1： 

4 31 2 62 3 31 3 23 3 43 1 3 21 1 3 42 2 4 3

输出样例#1： 

2811

说明

样例解释

K1 = (1*1+3)%2+1 = 1

K2 = (1*2+3)%4+1 = 2

K3 = (2*8+4)%3+1 = 3

对于100%的数据，1<=m,n,Si,Ei,Ci<=100000，0<=Ai,Bi<=100000，1<=Pi<=10000000，Xi为1到n的一个排列

 

题解

需要用差分数组

总而言之就是令$b[i]=a[i]-a[i-1]$

于是$\sum_{i=1}^n b[i]=a[i]$

可以通过前缀和来查询单个位置的值

每一个任务，就是给区间$[l,r]$每一个位置加上优先级$k$

等价于$b[l]+=k,b[r+1]-=k$

然后可以对每一个位置存下每个修改，然后在每个位置建主席树

记录下每个位置最后修改后所建主席树的编号，查询时直接使用

1 //minamoto 2 #include
     
       3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template
      
       inline bool cmax(T&a,const T&b){
   return a
       
        9) print(x/10);21     *o++=x%10+48;22 }23 const int N=2e5+5,M=5e6+5;24 int L[M],R[M],num[M],rt[N],spj[N<<1];ll sum[M];25 /*根据题意 1 <= Pi <= 1000000026 按照权值线段树的定义空间显然是不够的27 但考虑一共只有2m次插入，每次只增加log2m个节点28 所以我们这么开是没有问题的*/29 int ver[N<<1],Next[N<<1],head[N];30 int n,q,cnt=0,tot=0,fx,m;ll ans=1;31 void add(int u,int e){32     ver[++tot]=e,Next[tot]=head[u],head[u]=tot;33 }34 void update(int last,int &now,int l,int r,int x){35     if(!now) now=++cnt;36     num[now]=num[last]+(x<0?-1:1),sum[now]=sum[last]+x;37     /*因为用了差分数组，如果x为负说明少了一个数*/38     if(l==r) return;39     int mid=(l+r)>>1;40     if(abs(x)<=mid) R[now]=R[last],update(L[last],L[now],l,mid,x);41     else L[now]=L[last],update(R[last],R[now],mid+1,r,x);42 }43 ll query(int u,int l,int r,int k){44     if(l==r) return l*k;45     int mid=(l+r)>>1;46     if(k<=num[L[u]]) return query(L[u],l,mid,k);47     else return query(R[u],mid+1,r,k-num[L[u]])+sum[L[u]];48 }49 int main(){50     //freopen("testdata.in","r",stdin);51     n=read(),q=read();52     for(int i=1;i<=n;++i){53         int u=read(),v=read(),e=read();54         add(u,e),add(v+1,~e+1),cmax(fx,e);55     }56     for(int u=1;u<=n;++u){57         for(int i=head[u];i;i=Next[i])58         ++m,update(rt[m-1],rt[m],1,fx,ver[i]);59         spj[u]=m;60     }61     while(q--){62         int a,b,c,x;63         x=read(),a=read(),b=read(),c=read();64         ll k=(1ll*a*ans+b)%c+1;65         int w=rt[spj[x]];66         print(ans=(num[w]<=k)?sum[w]:query(w,1,fx,k));67         *o++='\n';68     }69     fwrite(obuf,o-obuf,1,stdout);70     return 0;71 }