题目描述
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
输出样例#1： 复制
2
8
11
说明
样例解释
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的一个排列
题解
首先我们来看一下我们面临的问题
1.我们要求前\(kth\)的优先级的和。
那么我们比较\(kth\)时就不能一直到\(left==right\)再\(return\)了。
可以考虑查询左子树 \(\le\) kth 时直接加上左子树再去查询右子树。
2.任务会消失。
考虑一手差分数组。
为什么？当任务出现时我们对任务出现的时间的数组+k，对任务消失的时间+1的数组-k，这样开始到消失的区间都加上了一个k值。
3.难调
壮士自重
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int N=100005;
ll tr[N<<6],n,m,q,p[N<<6],hs[N<<6],cnt,k;
struct nod{
ll v,t,hs,cnt;
}ch[N<<6];
struct node{
ll l,r,cnt,vi;
}t[N<<6];
ll read()
{
ll x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int build(int left,int right){
int mid=(left+right)>>1;
int root=++cnt;
if(left<right){
t[root].l=build(left,mid);
t[root].r=build(mid+1,right);
}
return root;
}
int update(int pre,int left,int right,int id){
int root=++cnt;
t[root].l=t[pre].l;t[root].r=t[pre].r;
t[root].vi=t[pre].vi+ch[id].v;
t[root].cnt=t[pre].cnt+ch[id].cnt;
int mid=(left+right)>>1;
if(left<right){
if(ch[id].hs<=mid) t[root].l=update(t[pre].l,left,mid,id);
else t[root].r=update(t[pre].r,mid+1,right,id);
}return root;
}
ll query(int pos,int left,int right,int kk){
int mid=(left+right)>>1;
if(left==right){if(t[pos].cnt!=0)return t[pos].vi/t[pos].cnt*kk;return 0;}
else {
if(t[t[pos].l].cnt>kk) return query(t[pos].l,left,mid,kk);
else return query(t[pos].r,mid+1,right,kk-t[t[pos].l].cnt)+t[t[pos].l].vi;
}
}
bool cmp(nod a,nod b){
return a.t<b.t;
}
int main()
{
n=read();q=read();
for(int i=1;i<=n;i++)
{
int x=read(),y=read();p[i]=read();
ch[++k].t=x;ch[k].cnt=1;ch[k].v=p[i];hs[k]=p[i];
ch[++k].t=y+1;ch[k].cnt=-1;ch[k].v=-p[i];hs[k]=p[i];
}
sort(p+1,p+n+1);
m=unique(p+1,p+n+1)-p-1;
tr[0]=build(1,m);
for(int i=1;i<=k;i++)
ch[i].hs=hs[i]=lower_bound(p+1,p+m+1,hs[i])-p;
sort(ch+1,ch+k+1,cmp);
for(int i=1;i<=k;i++)
{
int t1=ch[i].t,t2=ch[i-1].t;
while(t1-t2>1)
{
t2++;
tr[t2]=tr[t2-1];
}
tr[t1]=update(tr[ch[i-1].t],1,m,i);
}
ll last=1;
for(int i=1;i<=q;i++)
{
int x=read(),a=read(),b=read(),c=read();
ll k=1+(a*last+b)%c;
k=min(k,t[tr[x]].cnt);
printf("%lld\n",last=query(tr[x],1,m,k));
}
return 0;
}