《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; }