【题目】
传送门
题目描述：
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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 行，每行一个整数，表示查询结果。
样例数据：
输入
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
输出
2
8
11
备注：
【样例解释】
K1=(1*1+3)%2+1=1
K2=(1*2+3)%4+1=2
K3=(2*8+4)%3+1=3
【数据范围】
对于 50% 的数据，Ai=0
对于 100% 的数据，1≤m,n,Si,Ei,Ci≤100000；0≤Ai,Bi≤100000；1≤Pi≤10000000，Xi 为 1 到 n 的一个排列
【分析】
应该很容易可以分析出这是一道主席树题吧
我们以每个时间为根，以优先级为权值构建权值线段树
假如有一个 [
l
l
l，
r
r
r ] 时间内的任务，我们用差分的思想，在
l
l
l 上的出现次数
+
1
+1
+1，在
r
+
1
r+1
r+1 上的出现次数
−
1
-1
−1，这样按照时间从前往后扫一遍，就可以保证所有的时间上的值是对的
查询就和查区间第
k
k
k 大很像了，只不过我们要找前
k
k
k 个的值，其实只用再维护一个
s
u
m
sum
sum 就可以了
这道题好多大佬都用了离散化，但经实测，此题不用离散就可以过
还有要注意这种需要累加的题多半要开
l
o
n
g
  
l
o
n
g
long \;long
longlong
【代码】
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 100005
#define LogN 105
#define Max (int)1e+7+5
#define lc(x) tree[x].lc
#define rc(x) tree[x].rc
#define sum(x) tree[x].sum
#define num(x) tree[x].num
using namespace std;
int n,m,t;
int root[N];
struct node
{
int val,mark;
node(int val,int mark):val(val),mark(mark){}
};
vector<node>a[Max];
struct President_Tree
{
int lc,rc,num;
long long sum;
}tree[N*LogN];
void insert(int y,int &x,int l,int r,int val,int mark)
{
x=++t;
tree[x]=tree[y];
sum(x)+=val*mark;
num(x)+=mark;
if(l==r) return;
int mid=(l+r)>>1;
if(val<=mid) insert(lc(y),lc(x),l,mid,val,mark);
else insert(rc(y),rc(x),mid+1,r,val,mark);
}
long long query(int root,int l,int r,int k)
{
if(k>=num(root)) return sum(root);
if(l==r) return sum(root)/num(root)*k;
int mid=(l+r)>>1,delta=num(lc(root));
if(delta>=k) return query(lc(root),l,mid,k);
return query(rc(root),mid+1,r,k-delta)+sum(lc(root));
}
int main()
{
int s,e,p,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
scanf("%d%d%d",&s,&e,&p);
a[s].push_back(node(p,1));
a[e+1].push_back(node(p,-1));
}
for(i=1;i<=n;++i)
{
root[i]=root[i-1];
for(j=0;j<a[i].size();++j)
insert(root[i],root[i],1,Max,a[i][j].val,a[i][j].mark);
}
int a,b,c,x,k;
long long pre=1;
for(i=1;i<=m;++i)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=1+(a*pre+b)%c;
pre=query(root[x],1,Max,k);
printf("%lld\n",pre);
}
return 0;
}
