最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的
任务用三元组
\((S_i,E_i,P_i)\)
描述，
\((S_i,E_i,P_i)\)
表示任务从第
\(S_i\)
秒开始，在第
\(E_i\)
秒后结束（第
\(S_i\)
秒和
\(E_i\)
秒任务也在运行
），其优先级为
\(P_i\)
。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向
查询系统询问，第
\(X_i\)
秒正在运行的任务中，优先级最小的
\(K_i\)
个任务（即将任务按照优先级从小到大排序后取前
\(K_i\)
个
）的优先级之和是多少。特别的，如果
\(K_i\)
大于第
\(X_i\)
秒正在运行的任务总数，则直接回答第
\(X_i\)
秒正在运行的任务优先
级之和。上述所有参数均为整数，时间的范围在1到
\(n\)
之间（包含1和
\(n\)
）。
Input
输入文件第一行包含两个空格分开的正整数
\(m\)
和
\(n\)
，分别表示任务总数和时间范围。接下来
\(m\)
行，每行包含三个空格
分开的正整数
\(S_i\)
、
\(E_i\)
和
\(P_i(S_i≤E_i)\)
，描述一个任务。接下来
\(n\)
行，每行包含四个空格分开的整数
\(X_i\)
、
\(A_i\)
、
\(B_i\)
和
\(C_i\)
，
描述一次查询。查询的参数
\(K_i\)
需要由公式
\(K_i=1+(A_i*Pre+B_i) % C_i\)
计算得到。其中
\(Pre\)
表示上一次查询的结果，
对于第一次查询，
\(Pre=1\)
。
Output
输出共n行，每行一个整数，表示查询结果。
Sample Input
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
Sample Output
2
8
11
HINT
样例解释
\(K_1 = (1*1+3)%2+1 = 1\)
\(K_2 = (1*2+3)%4+1 = 2\)
\(K_3 = (2*8+4)%3+1 = 3\)
对于100%的数据，
\(1≤m,n,S_i,E_i,C_i≤100000\)
，
\(0≤A_i,B_i≤100000\)
，
\(1≤P_i≤10000000\)
，Xi为1到n的一个排列
题意：
中文题面，不解释
题解：
应该不难想到对于每一个点开一个权值线段树，但空间只有512MB，明显不行，而且如果我们把每个数暴力加入，肯定会TLE，所以需要一堆优化。
我们可以发现每个相隔的线段树，肯定有部分相同，所以我们可以用可持久化线段树来做了，同时对于一个数值，我们在左边那个时间点+1，在右边那个时间点
往后一个点
-1就可以了。我们开两个vector记录加减就行了。
好吧，还需要离散化。
最后我们对每一个询问求个区间和就行了。
这里有一个坑点，对于第K大那个点，我们需要加的不是这个值而是加上剩下的数乘上当前数。
然后就可以A掉了。
#include<bits/stdc++.h>
#define mid (l+(r-l)/2)
using namespace std;
const int N=100010;
int n,m,q;
vector<int>ad[N],dl[N];
int a[N];
int cnt,root[N],lson[N<<6],rson[N<<6],tr[N<<6];
long long sum[N<<6];
int build(int l,int r){
int rt=++cnt;
if(l==r)return rt;
lson[rt]=build(l,mid);
rson[rt]=build(mid+1,r);
return rt;
}
inline void pushup(int rt){
sum[rt]=sum[lson[rt]]+sum[rson[rt]];
}
int updata(int pre,int l,int r,int x,int z){
int rt=++cnt;
tr[rt]=tr[pre]+z;
if(l==r){
return rt;
}
lson[rt]=lson[pre];
rson[rt]=rson[pre];
if(x<=mid)lson[rt]=updata(lson[pre],l,mid,x,z);
else rson[rt]=updata(rson[pre],mid+1,r,x,z);
return rt;
}
long long query(int rt,int l,int r,int k){
if(l==r)return a[l]*min(k,tr[rt]);
if(tr[lson[rt]]>=k)return query(lson[rt],l,mid,k);
else return query(rson[rt],mid+1,r,k-tr[lson[rt]])+sum[lson[rt]];
}
void dfs(int rt,int l,int r){
if(!tr[rt]||sum[rt])return;
if(l==r){
sum[rt]=tr[rt]*a[l];
return;
}
dfs(lson[rt],l,mid);
dfs(rson[rt],mid+1,r);
pushup(rt);
}
inline int read(){
register int ret=0;register char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);ret=(ret<<1)+(ret<<3)+c-'0',c=getchar());
return ret;
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;++i){
int l=read(),r=read(),p=read();
ad[l].push_back(p);
dl[r+1].push_back(p);
a[i]=p;
}
sort(a+1,a+n+1);
m=unique(a+1,a+n+1)-a-1;
root[0]=build(1,m);
for(register int i=1;i<=n;++i){
root[i]=root[i-1];
for(vector<int>::iterator it=ad[i].begin();it!=ad[i].end();++it){
root[i]=updata(root[i],1,m,lower_bound(a+1,a+m+1,*it)-a,1);
}
for(vector<int>::iterator it=dl[i].begin();it!=dl[i].end();++it){
root[i]=updata(root[i],1,m,lower_bound(a+1,a+m+1,*it)-a,-1);
}
}
for(int i=0;i<=n;++i){
dfs(root[i],1,m);
}
long long last=1;
while(q--){
int x=read(),aa=read(),bb=read(),cc=read();
aa=((long long)aa*(last%cc)+bb)%cc+1;
last=query(root[x],1,m,aa);
printf("%lld\n",last);
}
}转载于:https://www.cnblogs.com/zhenglier/p/10100584.html