《P3168 [CQOI2015] 任务查询系统》

题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。

超级计算机中的任务用三元组 (si​,ei​,pi​) 描述，(si​,ei​,pi​) 表示任务从第 si​ 秒开始，在第 ei​ 秒后结束（第 si​ 秒和 ei​ 秒任务也在运行），其优先级为 pi​。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。

调度系统会经常向查询系统询问，第 xi​ 秒正在运行的任务中，优先级最小的 ki​ 个任务（即将任务按照优先级从小到大排序后取前 ki​ 个）的优先级之和是多少。

特别的，如果 ki​ 大于第 xi​ 秒正在运行的任务总数，则直接回答第 xi​ 秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在 [1,n] 之间。

输入格式

输入文件第一行包含两个空格分开的正整数 m 和 n，分别表示任务总数和时间范围。

接下来 m 行，每行包含三个空格分开的正整数 si​,ei​,pi​（si​≤ei​），描述一个任务。

接下来 n 行，每行包含四个空格分开的整数 xi​,ai​,bi​,ci​，描述一次查询。

本题强制在线。查询的参数 ki​ 需要由公式 ki​=1+(ai​×pre+bi​)modci​ 计算得到。其中 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)mod2+1=1；

k2​=(1×2+3)mod4+1=2；

k3​=(2×8+4)mod3+1=3。

【数据范围】

对于 100% 的数据，1≤m,n,ci​≤105，0≤ai​,bi​≤105，1≤si​≤ei​≤n，1≤pi​≤107，xi​ 为 1 到 n 的一个排列。

注：2024-12-28 加入一个 hack 数据，帖子链接。

代码实现：

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=100010; const int M=N*40; struct tsk{ int e, v, tg; bool operator < (const tsk &r) const{ return e<r.e; } tsk(int e,int v,int tg):e(e),v(v),tg(tg){} tsk(){} }b[N*3]; struct pt{ ll s, sz; int l, r; }tr[M]; int rt[N],n,m,cnt=1,tot=0,a[N]; int rd(){ int x=0,f=1;char ch=getchar(); while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();} while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } void ins(int &now,int x,int idx,int l=1,int r=n){ tr[cnt++]=tr[now];now=cnt-1; tr[now].sz+=(ll)idx; tr[now].s+=(ll)idx*a[x]; if (l==r)return; int mid=(l+r)>>1; if (x<=mid)ins(tr[now].l,x,idx,l,mid); else ins(tr[now].r,x,idx,mid+1,r); } ll qry(int now,int k,int l=1,int r=n){ if (l==r)return tr[now].s/tr[now].sz*(ll)k; int mid=(l+r)>>1; int t=tr[tr[now].l].sz; if (k<=t)return qry(tr[now].l,k,l,mid); else return tr[tr[now].l].s + qry(tr[now].r,k-t,mid+1,r); } int main(){ m=rd(),n=rd(); for (int i=1;i<=m;i++){ int x=rd(),y=rd(),z=rd(); b[++tot]=tsk(x,z,1); b[++tot]=tsk(y+1,z,-1); a[i]=z; } sort(a+1,a+m+1); sort(b+1,b+tot+1); rt[0]=0; for (int i=1,j=1;i<=n;i++){ rt[i]=rt[i-1]; for (;j<=tot && b[j].e==i;j++){ int rk=lower_bound(a+1,a+n+1,b[j].v)-a; ins(rt[i],rk,b[j].tg); } } ll ans=1; for (int i=1;i<=n;i++){ ll x=rd(),A=rd(),B=rd(),C=rd(); ll k=(A*ans+B)%C+1; if (k>=tr[rt[x]].sz)ans=tr[rt[x]].s; else ans=qry(rt[x],k); printf("%lld\n",ans); } return 0; }