洛谷P3168 [CQOI2015]任务查询系统

题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组\((S_i,E_i,P_i)\)描述，\((S_i,E_i,P_i)\)表示任务从第Si秒开始，在第\(E_i\)秒后结束（第\(S_i\)秒和\(E_i\)秒任务也在运行），其优先级为\(P_i\)。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第\(X_i\)秒正在运行的任务中，优先级最小的\(K_i\)个任务（即将任务按照优先级从小到大排序后取前\(K_i\)个）的优先级之和是多少。特别的，如果\(K_i\)大于第\(X_i\)秒正在运行的任务总数，则直接回答第\(X_i\)秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

输入输出格式

输入格式：

输入文件第一行包含两个空格分开的正整数\(m\)和\(n\)，分别表示任务总数和时间范围。接下来\(m\)行，每行包含三个空格分开的正整数\(S_i\)、\(E_i\)和\(P_i(S_i \leq E_i)\)，描述一个任务。接下来\(n\)行，每行包含四个空格分开的整数\(X_i\)、\(A_i\)、\(B_i\)和\(C_i\)，描述一次查询。查询的参数\(K_i\)需要由公式 \(K_i=1+(A_i \times Pre+B_i)\) \(mod\) \(C_i\)计算得到。其中\(Pre\)表示上一次查询的结果，对于第一次查询，\(Pre=1\)。

输出格式：

输出共\(n\)行，每行一个整数，表示查询结果。

思路

主席树
以每一个时间点建立主席树版本，主席树维护一个数组\(a_i\)的区间和，\(a_i\)表示有几个优先级为\(i\)的任务，同时通过有几个优先级为\(i\)的任务也就可以维护区间优先级之和。
对于一开始的任务，将所有的任务的开始时间和结束时间在一起进行排序，然后对于排序后的每个\(S_i\)，对于时间点为\(S_i\)的主席树版本在数组\(a_i\)的第\(P_i\)个位置上加一，对于每一个\(E_i\)，对于时间点为\(E_i\)的主席树版本在数组\(a_i\)的第\(P_i\)个位置上减一。
查询时由于维护了区间和，那么就可以找到第\(k\)小的任务的优先级是多少，同时返回维护的优先级之和即可。

CODE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10000010
#define MAXM 200010
typedef long long int lli;
struct Task{
    lli pos,p;
    Task(){}
    Task(lli pos,lli p):pos(pos),p(p){}
    bool operator < (const Task &a) const{
        return pos<a.pos;
    }
}task[MAXM];
lli ch[MAXN][2],rt[MAXN],sz[MAXN],id[MAXM];
lli sum[MAXN];
lli i,j,k,m,n,x,y,ncnt,a,b,c,maxn;
lli ans;
char readc;
void read(lli &n){
    while((readc=getchar())<48||readc>57);
    n=readc-48;
    while((readc=getchar())>=48&&readc<=57) n=n*10+readc-48;
}
void update(lli &cur,lli pre,lli l,lli r,lli p,lli upd){
    cur=++ncnt;
    ch[cur][0]=ch[pre][0];
    ch[cur][1]=ch[pre][1];
    sz[cur]=sz[pre],sum[cur]=sum[pre];
    if(l==r){
        sz[cur]+=upd;
        sum[cur]=sz[cur]*l;
        return;
    }
    lli mid=(l+r)>>1;
    if(p<=mid) update(ch[cur][0],ch[pre][0],l,mid,p,upd);
    else update(ch[cur][1],ch[pre][1],mid+1,r,p,upd);
    sz[cur]=sum[cur]=0;
    if(ch[cur][0]) sz[cur]+=sz[ch[cur][0]],sum[cur]+=sum[ch[cur][0]];
    if(ch[cur][1]) sz[cur]+=sz[ch[cur][1]],sum[cur]+=sum[ch[cur][1]];
}
lli query(lli cur,lli l,lli r,lli k){
    if(!k) return 0;
    if(l==r){
        return sum[cur]/sz[cur]*min(k,sz[cur]);
    }
    if(sz[cur]<=k){
        return sum[cur];
    }
    lli mid=(l+r)>>1;
    lli ans=0;
    if(!ch[cur][0]){
        return query(ch[cur][1],mid+1,r,k);
    }
    if(!ch[cur][1]){
        return query(ch[cur][0],l,mid,k);
    }
    if(sz[ch[cur][0]]<=k){
        ans+=query(ch[cur][0],l,mid,sz[ch[cur][0]]);
        k-=sz[ch[cur][0]];
    }else{
        return query(ch[cur][0],l,mid,k);
    }
    ans+=query(ch[cur][1],mid+1,r,k);
    return ans;
}
int main(){
    read(m),read(n);
    maxn=0;
    for(i=1;i<=m;i++){
        read(task[i].pos),read(task[i+m].pos);
        task[i+m].pos++;
        read(task[i].p); task[i+m].p=(-1)*task[i].p;
        maxn=max(maxn,task[i].p);
    }
    sort(task+1,task+2*m+1);
    for(i=1;i<=2*m;i++){
        if(task[i].p>0){
            update(rt[i],rt[i-1],1,maxn,task[i].p,1);
        }else{
            update(rt[i],rt[i-1],1,maxn,-task[i].p,-1);
        }
    }
    id[0]=0;
    for(i=1,j=1;i<=n;i++){
        while(task[j].pos==i){
            j++;
        }
        id[i]=j-1;
    }
    ans=1;
    for(i=1;i<=n;i++){
        read(x),read(a),read(b),read(c);
        ans%=c;
        y=1+((a*ans)%c+b)%c;
        ans=query(rt[id[x]],1,maxn,y);
        printf("%lld\n",ans);
    }
    return 0;
}

洛谷P3168 [CQOI2015]任务查询系统

原文：https://www.cnblogs.com/linxif2008/p/10347386.html