3932: [CQOI2015]任务查询系统
Description
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。
超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。
Input
输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。
接下来m行，每行包含三个空格分开的正整数Si、Ei和Pi(Si≤Ei)，描述一个任务。
接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci
计算得到。其中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
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
8
11
HINT
样例解释
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的一个排列
美妙の主席树（虽然蒟蒻wy打得不是很美妙。。。）
#include<cstdio>
#include<algorithm>
#define MaxN 100010
#define MaxT 5000010
using namespace std;
int N,Q,M,tot;
struct point{
int l,r,size;
long long sum;
}P[MaxT];
struct xx{
int key,s,w;
}L[2*MaxN];
int A[MaxN];
int Li[MaxN];
int root[MaxN];
int cmp(const xx &a,const xx &b){
return a.key<b.key || a.key==b.key && a.s>b.s;
}
void Discretization(){
sort(Li+1,Li+M+1);
M=unique(Li+1,Li+M+1)-Li-1;
for (int i=1;i<=N;++i)
A[i]=lower_bound(Li+1,Li+M+1,A[i])-Li;
}
void Change(int y,int &x,int l,int r,int p,int w,int t){
P[x=++tot]=P[y];
P[x].size+=w;
P[x].sum+=t*w;
if (l==r) return;
int mid=(l+r)/2;
if (p<=mid) Change(P[y].l,P[x].l,l,mid,p,w,t);
else Change(P[y].r,P[x].r,mid+1,r,p,w,t);
}
long long find(int x,int l,int r,int w){
if (w<=0) return 0;
if (P[x].size<=w)
return P[x].sum;
if (l==r)
return (long long)w*Li[l];
int mid=(l+r)/2;
long long s=0;
s+=find(P[x].l,l,mid,w);
s+=find(P[x].r,mid+1,r,w-P[P[x].l].size);
return s;
}
int main(){
scanf("%d%d",&N,&Q);
for (int i=1;i<=N;++i){
scanf("%d%d",&L[i*2-1].key,&L[i*2].key);
++L[i*2].key;
L[i*2-1].s=1; L[i*2].s=-1;
L[i*2-1].w=L[i*2].w=i;
scanf("%d",&A[i]);
Li[++M]=A[i];
}
Discretization();
sort(L+1,L+2*N+1,cmp);
for (int k=1;k<=2*N;++k){
for (int i=L[k-1].key+1;i<L[k].key&&i^1;++i)
root[i]=root[i-1];
Change(root[L[k-1].key],root[L[k].key],1,M,A[L[k].w],L[k].s,Li[A[L[k].w]]);
}
for (int i=L[2*N].key+1;i<=Q+1;++i)
root[i]=root[i-1];
long long ans=1;
for (;Q--;){
int x,A,B,C;
scanf("%d%d%d%d",&x,&A,&B,&C);
int k=1+(ans*A+B)%C;
ans=find(root[x],1,M,k);
printf("%lld\n",ans);
}
}
评论 (0)
