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

· · 题解

看到大佬们都在用主席树写，但是蒟蒻难以理解这样写的原因，于是只好写了个更容易理解的线段树合并。

前置知识

差分（不会差分写这题？）。

离散化。（不会离散化写这题？）。

权值线段树（其实就是线段树维护桶）。

线段树合并（不会的先写这题）。

思路

差分+权值线段树+线段树合并。

题目要求求每一秒权值前 k 小的任务的权值和，这不正是权值树该干的吗?

于是想到在每一个时间点开一个权值树，维护任务总数 cnt 用于求前 k 小，维护优先级总和 sum 用于求答案。

题目要求区间修改，于是想到利用差分思想。
将 s 秒的权值树对应位置的 cnt+1，sum+p。
将 e+1 秒的权值树对应位置的 cnt-1，sum-p。

最后将权值树按照时间顺序合并，第一秒与第二秒合并，然后将第二秒与第三秒合并，以此类推，即可得到修改之后每一秒中任务的数据（类比差分数组求前缀和得到原数组）。

查询时直接在第 x 秒的权值树上查询前 k 小的优先级总和即可。

这时有巨佬就要发问了，优先级最大值为 10^{7}，内存怎么不炸？

我们来看，任务总数为 m，也就是至多有 m 种不同的优先级，我们只对于这些优先级进行操作，对于不存在的优先级不需要处理（就相当于优先级的范围为 1 ~ m），这就给了我们离散化的机会。离散化应该都会吧。
然后动态开点，只有当某颗权值树上的某个节点被使用到时才开一个节点，这样就不存在浪费空间的问题了。

具体细节看代码。

复杂度分析

每次利用动态开点和离散化，每加入一个新的任务时，只增加至多 2\cdot \log_{2}{m} 个节点，共有 m 个任务，所以空间复杂度 O(2\cdot m\log_{2}{m})。这题的空间非常充裕，完全够用。

每次加入一个任务时至多新开 2\cdot \log_{2}{m} 个节点，所以单次加入任务的复杂度为 O(\log_{2}{m})，共修改 m 次，建树时间复杂度 O(m\log_{2}{m})。

合并假设将每个端点都与另一个端点合并，时间复杂度与空间复杂度一致，为 O(m\log_{2}{m})。

查询复杂度 O(\log_{2}{m}) （这个不用过多解释了吧）。

总时间复杂度：

O(m\log_{2}{m})

可以通过此题。

代码

#include<bits/stdc++.h>
#define ll long long
#define dd double
#define lson c[id].ls
#define rson c[id].rs
#define mid ((l+r)/2)
using namespace std;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
const ll N=1e5+9;
ll b[N],q;//离散化
ll s[N],e[N],a[N];//存储任务信息
ll n,m,pre=1;
ll ccnt;//动态开点
struct NODE{
    ll ls,rs;
    ll cnt,sum;//任务数，优先级总和
}c[N*50];//权值树
ll root[N];//第i秒对应的权值树的根节点
ll getid(ll x){
    return lower_bound(b+1,b+q+1,x)-b;
}
void pu(ll id){//push_up
    c[id].cnt=c[lson].cnt+c[rson].cnt;
    c[id].sum=c[lson].sum+c[rson].sum;
}
void change(ll &id,ll l,ll r,ll x,ll vel){//某秒优先级为x的任务增加或减少1
    if(!id){
        id=++ccnt;
    }
    if(l==r){
        c[id].cnt+=vel;
        c[id].sum+=b[x]*vel;
        return;
    }
    if(x<=mid){
        change(lson,l,mid,x,vel);
    }
    else{
        change(rson,mid+1,r,x,vel);
    }
    pu(id);
}
ll hebing(ll u,ll v,ll l,ll r){//把v合并到u上
    if(u==0||v==0){
        return u+v;
    }
    if(l==r){
        c[u].cnt+=c[v].cnt;
        c[u].sum+=c[v].sum;
        return u;
    }
    c[u].ls=hebing(c[u].ls,c[v].ls,l,mid);
    c[u].rs=hebing(c[u].rs,c[v].rs,mid+1,r);
    pu(u);
    return u;
}
void cacl(){//合并差分数据得到原数据
    for(int i=1;i<=n;i++){//按照时间顺序合并
        root[i]=hebing(root[i],root[i-1],1,q);
    }
}
ll qu(ll id,ll l,ll r,ll k){//查询某秒优先级最小的k个任务的优先级之和
    if(l==r){
        if(c[id].cnt>k){
            return (c[id].sum/c[id].cnt)*k;//由于叶子节点只表示一种优先级，所以可以算出每个任务的优先级然后乘以k出答案
        }
        else{
            return c[id].sum;
        }
    }
    if(k<=c[lson].cnt){
        return qu(lson,l,mid,k);
    }
    else{
        return qu(rson,mid+1,r,k-c[lson].cnt)+c[lson].sum;
    }
}
int main(){
    m=read();
    n=read();
    for(int i=1;i<=m;i++){
        s[i]=read(),e[i]=read(),a[i]=read();
        b[++q]=a[i];
    }
    sort(b+1,b+q+1);
    q=unique(b+1,b+q+1)-b-1;//离散化
    for(int i=1;i<=m;i++){
        change(root[s[i]],1,q,getid(a[i]),1);
        change(root[e[i]+1],1,q,getid(a[i]),-1);//差分思想修改
    }
    cacl();//线段树合并
    for(int i=1;i<=n;i++){
        ll x=read(),a=read(),b=read(),c=read();
        ll k=1+(a*pre+b)%c;
        pre=qu(root[x],1,q,k);
        write(pre);
        putchar('\n');
    }
    return 0;
}

本题解已通过 hack，记录。