[CQOI2015]任务查询系统

题目描述

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

输入输出格式

输入格式：

 

输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，对于第一次查询，Pre=1。

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

4 31 2 62 3 31 3 23 3 43 1 3 21 1 3 42 2 4 3

输出样例#1：

2811

说明

样例解释

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的一个排列

数据结构：主席树

联想poj 2104 K-th Number 

poj那道题找区间第k小的数，本题是找区间前k小的数的和

所以，先离散化优先级，以时间为下标，以优先级为区间建立主席树。

维护每个时间的优先级总和 sum ，正在进行的任务数量 countt

前缀和转化，开始时间+，结束时间后面1个-

所以，对任务的开始结束按时间从小到大的顺序插入

注意1：一定要排序

否则，由于同一任务插入后接着删除，加减抵消，主席树中sum[x]最后剩下的是x时间的最后一项任务的优先级，而不是x时间所有任务的优先级总和

在插入时，

注意2：没有作为任务的开始和结束出现的时间点，要用前一个时间点给它赋值

否则，询问时如果问到这样的时间点x，由于没有以x为根建立线段树，root[x]=0，查询结果也是0

具体实现参照代码中标注“important”那一行

就是枚举时间范围，不管会不会出现先都给它的root赋值为前一个的root，然后判断这一时间点是否在任务中出现过，出现过直接覆盖原来的赋值

由于前面对任务的时间排了序，所以除去插入的时间，是O（时间范围）的

这一项没想到，卡了一晚上

然后就查询吧，然而这里还有一个坑~

注意3：当到达叶子节点时，答案不能直接加上叶子节点的优先级之和

因为有可能叶子节点的任务数>k，所以答案+叶子节点的优先机制和/叶子节点的任务数*k

还有一个小细节：40*n的空间

平常都是20*n，这次因为对每个任务都有2个时间点，所以再翻倍

至于平常为什么是20*n，不知道。。。。。。。

求助路过的大佬

#include
     
      #include
      
       #include
       
        #define N 100001using namespace std;int m,n,tot,p[N],hash[N];int root[N*4],lch[N*40],rch[N*40],cnt,countt[N*40];long long sum[N*40];long long ans;struct node{    int p,pos,co;}q[N*2];void discrete(){    sort(p+1,p+m+1);    tot=unique(p+1,p+m+1)-(p+1);    for(int i=1;i<=m;i++) hash[i]=lower_bound(p+1,p+tot+1,hash[i])-p;}inline void insert(int pre,int & now,int l,int r,int w,int c){    sum[now=++cnt]=sum[pre]+(long long)c*p[w];    countt[now]=countt[pre]+c;    if(l==r) return;    int mid=l+r>>1;    if(w<=mid)     {        rch[now]=rch[pre];        insert(lch[pre],lch[now],l,mid,w,c);    }    else     {        lch[now]=lch[pre];        insert(rch[pre],rch[now],mid+1,r,w,c);    }}inline void query(int y,int l,int r,long long k){    if(l==r)     {        ans+=sum[y]/countt[y]*k;    return;    }    if(countt[y]<=k)     {        ans+=sum[y];    return;    }    int mid=l+r>>1,tmp=countt[lch[y]];    if(k<=tmp) query(lch[y],l,mid,k);    else    {        ans+=sum[lch[y]];        query(rch[y],mid+1,r,k-tmp);    }}inline bool comp(node k,node l){    return k.pos<=l.pos;}int main(){    scanf("%d%d",&m,&n);    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&q[i*2-1].pos,&q[i*2].pos,&p[i]);         q[i*2].pos++;        hash[i]=p[i];    }    discrete();    for(int i=1;i<=m;i++)     {        q[i*2-1].p=hash[i];        q[i*2].p=hash[i];        q[i*2-1].co=1;        q[i*2].co=-1;        }    sort(q+1,q+2*m+1,comp);    int j=1;    for(int i=1;i<=n;i++)     {         root[i]=root[i-1];//This is very important         while(j<=2*m&&q[j].pos==i)         {             insert(root[i],root[i],1,tot,q[j].p,q[j].co);             j++;        }     }    long long p=1,a,b,c,k;    int x;    for(int i=1;i<=n;i++)    {        ans=0;        scanf("%d",&x);        scanf("%lld%lld%lld",&a,&b,&c);        k=1ll+(a*p+b)%c;        if(k>=countt[root[x]]) ans=sum[root[x]];        else query(root[x],1,tot,k);        printf("%lld\n",ans);        p=ans;    }}
       
      
     

做了一下午没做出来，晚上问了学长，原因：

离散化了时间，即以时间为下标，又以时间为区间建立主席树

最后写到查询的时候，要从区间内出现过的优先级中去前k小

当时只想到暴力搜索，或优先队列

太麻烦，不写了

根本原因还是对主席树理解不透彻

#include
      
       #include
       
        #include
        
         #define N 100001using namespace std;vector
         
          t[N];bool v[N];int m,n,tot,p[N],e[2*N],hash[2*N];int root[N],lch[N*20],rch[N*20],cnt,countt[N*20];long long sum[N*20];long long ans;struct node{    int p,pos,co;}q[N*2];void discrete(){    sort(e+1,e+2*m+1);    tot=unique(e+1,e+2*m+1)-(e+1);    for(int i=1;i<=2*m;i++) hash[i]=lower_bound(e+1,e+tot+1,hash[i])-e;}inline void insert(int pre,int & now,int l,int r,int w,int pos,int jj){    sum[now=++cnt]=sum[pre]+w;    countt[now]=countt[pre]+jj;    if(l==r) return;    int mid=l+r>>1;    if(pos<=mid)     {        rch[now]=rch[pre];        insert(lch[pre],lch[now],l,mid,w,pos,jj);    }    else     {        lch[now]=lch[pre];        insert(rch[pre],rch[now],mid+1,r,w,pos,jj);    }}inline void query(int y,int l,int r,int k,int opl,int opr){    if(countt[y]<=0) return;    /*if(countt[y]<=k)     {        ans+=sum[y];        return;    }*/    if(opl<=l&&opr>=r)    {        if(k>=count[y]) ans+=sum[y];        else         {            for(int i=l;i<=r;i++)            if(!v[i])             {                sort(t[i].begin(),t[i].end());                 v[i]=true;                ans+=k个。。。。。             }                    }    }    if(l==r)     {            if(k
          
           >1/*,tmp=countt[lch[y]]*/;    if(time<=/*tmp*/mid) query(lch[y],l,mid,k,time);    else     {        //ans+=sum[lch[y]];        query(rch[y],mid+1,r,/*k-tmp*/k,time);    }    }inline bool cmp(node k,node l){    /*if(k.pos
           
            l.p) return 1; return 0;*/ return k.pos<=l.pos;}int main(){ /*freopen("cqoi15_query1.in","r",stdin); freopen("cqoi15_query.out","w",stdout);*/ scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i*2-1],&e[i*2],&p[i]); t[e[i*2-1]].push_back(p[i]); hash[i*2-1]=e[i*2-1];hash[i*2]=e[i*2]; } discrete(); for(int i=1;i<=m;i++) { q[i*2-1].p=p[i]; q[i*2-1].pos=hash[i*2-1]; q[i*2].p=-p[i]; q[i*2].pos=hash[i*2]+1; q[i*2-1].co=1; q[i*2].co=-1; } sort(q+1,q+2*m+1,cmp); for(int i=1;i<=2*m;i++) insert(root[q[i-1].pos],root[q[i].pos],1,tot+1,q[i].p,q[i].pos,q[i].co); int p=1,a,b,c,x,k; for(int i=1;i<=n;i++) { ans=0; scanf("%d%d%d%d",&x,&a,&b,&c); k=1+(a*p+b)%c; x=upper_bound(e+1,e+tot+1,x)-e-1; query(root[x],1,m,k,1,x); printf("%lld\n",ans); p=ans; }}