题解 P3168 【[CQOI2015]任务查询系统】

· · 题解

任务查询系统

题意简述

现在有一群任务,每个任务都有开始和结束的时间和一个优先级,给你所有任务的开始结束时间和优先级,问你在某个时间点优先级最小的k个的优先级的和是多少.

题目分析

1.区间加,区间减,单点求值.

想到区间加减,单点求值,我们就能想到差分数组.

如果把区间排序之后,是不是就是可以做前缀和完成?

所以本文提出的是一种前缀和树

但是这不是一个数,而是一群数,很自然想到树形结构.

2.查询k小.

线段树就能实现.

3.空间512M.

如果每一个都开一个线段树肯定会炸啊,所以我们可以用这个奇怪的主席树优化空间.

4.优先级多,n少

至此我们就能得到最终的解法:先离散化,然后用主席树维护优先级,做前缀和主席树

问题解决

首先做离散化:

bool comp1(Sin c,Sin v){return c.val<v.val;}

sort(a+1,a+m+1,comp1);
for(int i=1;i<=m;++i){
    if(a[i].val!=a[i-1].val)
        ++cntrank;
    a[i].rank=cntrank;
}

然后考虑到我们用的是前缀和,所以先按时间排序,这时候终止时间就是原来的任务结束时间+1了.

bool comp2(Sto c,Sto v){return c.pos<v.pos;}

for(int i=1;i<=m;++i){
    b[2*i-1].rank=a[i].rank;
    b[2*i-1].rnum=a[i].val;
    b[2*i-1].pos=a[i].from;
    b[2*i-1].ltt=1;
    b[2*i].pos=a[i].to+1;
    b[2*i].rnum=a[i].val;
    b[2*i].rank=a[i].rank;
    b[2*i].ltt=0;
}
sort(b+1,b+2*m+1,comp2);

之后就到了简单的前缀和主席树的构造了.

我们维护两个指针,一个代表现在处理到哪一个b,另一个代表现在处理到哪一个时间点了.

可以得到:

cntb=1;
for(int i=1;i<=n;++i){
    for(;i==b[cntb].pos;++cntb)
        //在主席树上加上/减去它的值
}

但是还有个问题,这个问题可能卡到你80上不去.

如果我去重了之后,排名为q的点有w个,但是我要找k个,k<w,你就会return 奇奇怪怪的东西.这时候两个解决方法:

1.不去重,这样自然就能保证都是1了.

2.特判最终节点,如果是的话,就return k个它的值.

实现:

1.算排名的时候这样算

for(int i=1;i<=m;++i)
    a[i].rank=i

2.查询函数这样写

long long query(int num,int ln,int rn,int k){
    if(ln==rn)  return k*sum[num]/total[num];
    //do sth.
}

亲测两种都可以.

如果大家是卡在80,可以现在回去改一下试试.

对拍Code

#include<bits/stdc++.h>
#define mid ((ln+rn)>>1)
#define lss ls[num],ln,mid
#define rss rs[num],mid+1,rn
using namespace std;
const int Nmax = 400010;
int ls[Nmax<<5],rs[Nmax<<5],cnt,root[Nmax<<3];long long sum[Nmax<<5],total[Nmax<<5];
void Build(int &num,int ln,int rn){
    num=++cnt;
    if(ln==rn)
        return;
    Build(lss);
    Build(rss);
}
void change(int &num,int old,int ln,int rn,int pos,int val,int yy){
    num=++cnt;
    sum[num]=sum[old]+val*yy;
    total[num]=total[old]+1*yy;
    ls[num]=ls[old];
    rs[num]=rs[old];
    if(ln==rn)  
        return;
    if(pos<=mid)    
        change(ls[num],ls[old],ln,mid,pos,val,yy);
    else          
        change(rs[num],rs[old],mid+1,rn,pos,val,yy);
}
void copy(int &num,int old){
    num=++cnt;
    ls[num]=ls[old];
    rs[num]=rs[old];
    total[num]=total[old];
    sum[num]=sum[old];
}
long long query(int num,int ln,int rn,int k){
    if(ln==rn)  
        return k*sum[num]/total[num];
    if(total[num]<=k)   
        return sum[num];
    if(total[ls[num]]>=k)   
        return  query(ls[num],ln,mid,k);
    return query(rs[num],mid+1,rn,k-total[ls[num]])+
           sum[ls[num]];
}
int m,n,cntrank,cntb=1;
long long last=1;
struct Sin{
    int from,to;
    long long val;
}a[Nmax];
struct Sto{
    int pos,rank;
    long long rnum;
    bool ltt;
}b[Nmax<<1];
bool comp1(Sin c,Sin v){
    return c.val<v.val;
}
bool comp2(Sto c,Sto v){
    return c.pos<v.pos;
}
long long p1,p2,p3,p4,p5;
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;++i)
        scanf("%d%d%lld",&a[i].from,&a[i].to,&a[i].val);
    sort(a+1,a+m+1,comp1);
    for(int i=1;i<=m;++i){
        if(a[i].val!=a[i-1].val)
            ++cntrank;
        b[2*i-1].rank=cntrank;
        b[2*i-1].rnum=a[i].val;
        b[2*i-1].pos=a[i].from;
        b[2*i-1].ltt=1;
        b[2*i].pos=a[i].to+1;
        b[2*i].rnum=a[i].val;
        b[2*i].rank=cntrank;
        b[2*i].ltt=0;
    }
    Build(root[0],1,cntrank);
    sort(b+1,b+2*m+1,comp2);
    b[2*m+1].pos=0;
    for(int i=1;i<=n;++i){
        copy(root[i],root[i-1]);
        //这一行确实有点长
        for(;i==b[cntb].pos;++cntb)
            change(root[i],root[i],1,cntrank,b[cntb].rank,b[cntb].rnum,(b[cntb].ltt?1:-1));
    }
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld%lld",&p1,&p2,&p3,&p4);
        p5=1+(p2*last+p3)%p4;
        last=query(root[p1],1,cntrank,p5);
        printf("%lld\n",last);
    }
    return 0;
}