题目描述
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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的一个排列
分析：
据说这道题可以用暴力A？
但我们现在是高端人士
需要用高nan端xie的算法
A掉这些复zhi杂zhang的题
主席树.nd
tip
开ll
好好读题
m是任务总数，n是时间范围
搞不清为什么传参的时候，要传m
Ans：我们在一开始的时候把优先级离散成了一个n级别的序列
（毕竟有多少任务就有多少个离散后的排名啊）
新建线段树代表时间的推移
而每一棵线段树中，维护的都是各个优先级，从小到大排序
只有这样，在查询的时候我们才能找到第k大
所以传入的一定是n（不同的优先级）
写完之后发现insert的&好像一点用都没有
tree里的元素并没有跟着改变
后来才发现是这句话写错了
这里写代码片
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int N=100010;
struct node{
ll v,sum,l,r;
};
node tree[N*160];
ll root[N<<1],tot=0,top=0;
struct nd{
int x,v,type,num;
};
nd po[N<<1];
ll zz[N],id[N],num[N],pre=1,temp;
int n,m;
int cmp1(const int a,const int b){return zz[a]<zz[b];}
int cmp2(const nd &a,const nd &b){return a.x<b.x;}
int ask(ll bh,int l,int r,ll k)
{
if (l==r)
{
return temp+=tree[bh].sum;
}
int mid=(l+r)>>1;
ll t=tree[tree[bh].l].v; //有多少个元素
if (t>=k) return ask(tree[bh].l,l,mid,k);
else
{
temp+=tree[tree[bh].l].sum; //不要忘了把值加上
return ask(tree[bh].r,mid+1,r,k-t);
}
}
void insert(ll &now,int l,int r,int wz,int val,int zl) //位置，优先值，种类
{
top++;
tree[top]=tree[now]; //新建节点
now=top; //
tree[now].v+=zl; //子树中有多少个元素
tree[now].sum+=val;
if (l==r) return;
int mid=(l+r)>>1;
if (wz<=mid) insert(tree[now].l,l,mid,wz,val,zl);
if (wz>mid) insert(tree[now].r,mid+1,r,wz,val,zl);
}
void print()
{
int i,j;
for (i=1;i<=top;i++)
printf("%d: ls:%lld rs:%lld v:%lld sum:%lld
",i,tree[i].l,tree[i].r,tree[i].v,tree[i].sum);
puts("");
}
int main()
{
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z); //把每个任务拆成两个
zz[i]=z; id[i]=i;
if (u>w) swap(u,w);
tot++;
po[tot].x=u; po[tot].v=z; po[tot].type=1; //加入
tot++;
po[tot].x=w+1; po[tot].v=-z; po[tot].type=-1; //删除
}
sort(id+1,id+1+m,cmp1); //把优先级离散化,抽象成了排名
for (int i=1;i<=m;i++) num[id[i]]=i;
for (int i=1;i<=tot;i+=2)
po[i].num=num[(i+1)/2],po[i+1].num=num[(i+1)/2];
sort(po+1,po+1+tot,cmp2); //按时间排序
int j=1;
for (int i=1;i<=n;i++) //n是时间范围
{
root[i]=root[i-1];
while (po[j].x==i) insert(root[i],1,m,po[j].num,po[j].v,po[j].type),j++;
// print();
}
for (int i=1;i<=n;i++)
{
int u,a,b,c;
scanf("%d%d%d%d",&u,&a,&b,&c);
int k=1+(a*pre+b)%c;
temp=0;
pre=ask(root[u],1,m,k);
printf("%lld
",pre);
}
return 0;
}