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

· · 题解

来自我的博客：http://blog.csdn.net/YihAN\_Z/article/details/53998106

欢迎到本沙茶的博客转转

题目大意：有n个任务持续m秒，每个任务从si秒开始到ei秒结束且有一个优先级pi，有m个询问，回答第xi秒时正在执行的任务中优先级前k小和，强制在线。

根据时间的变化，任务会开始或结束。我们想知道任一时刻任务的执行情况，这里我们就需要用到可持久化数据结构。对于这道题，我们可以维护一个权值线段树^1。

可持久化数据结构，暴力地想就是每个版本完全复制一个保存起来，但是空间不够用。

如果每次只是修改一个点的话，在线段树中会有logn个点的信息发生变化，其余仍然和前一秒一样，这样的话直接复用前一秒的版本，空间复杂度从n^2logn变为nlog^2n.

具体如何实现呢？

先在第0秒创建一个空版本。把每一个任务分成两个操作：在第si秒插入在ei+1秒删除。把操作按照时间排序然后构建每一秒的权值线段树。插入或删除时要新建结点。

权值范围太大这里需要离散化。

在复制结点的时候不要忘记复制儿子指针。

k要开long long。

线段树查找第k大时递归到点树上要进行讨论。

改了一上午。离散化辣眼睛凑合看吧0.0

#include <cstdio>
#include <algorithm>
#include <queue>
#define N 100005
#define INF 1e7
using namespace std;
typedef long long LL;
inline int abs(int x) {return x>0 ? x : -x;}
int n,m;
LL ans=1;
struct Segment_Tree{
    Segment_Tree *ch[2];
    int s;
    LL sum;
    Segment_Tree(Segment_Tree* x) {
        if(x==NULL) s=0 , sum=0 , ch[0]=ch[1]=NULL;
        else s=x->s , sum=x->sum , ch[0]=x->ch[0] , ch[1]=x->ch[1];
    }
}*root[N];
int disc[N];
typedef Segment_Tree ST;
void Init(ST*& x,int l,int r) {
    x=new ST(NULL);
    if(l==r) return ;
    int mid=l+r>>1;
    Init(x->ch[0],l,mid); Init(x->ch[1],mid+1,r);
    return ;
}
void Insert(ST*& x,int v,int l,int r) {
    ST* cach=x;
    x=new ST(cach);
    int flag=(v>0?1:-1);
    x->s+=flag , x->sum+=flag*disc[abs(v)];
    if(l==r) return ;
    int mid=l+r>>1;
    if(abs(v)<=mid) Insert(x->ch[0],v,l,mid);
    else Insert(x->ch[1],v,mid+1,r);
    return ;
}
LL Query(ST* x,int k,int l,int r) {
    if(k>=x->s) return x->sum;
    if(l==r) return (x->sum/x->s)*k;
    int mid=l+r>>1;
    if(x->ch[0]!=NULL) {
        if(x->ch[0]->s>=k) return Query(x->ch[0],k,l,mid);
        return x->ch[0]->sum+Query(x->ch[1],k-x->ch[0]->s,mid+1,r);
    }
    return Query(x->ch[1],k,mid+1,r);
}
struct Operation {
    int ord,val;
    Operation(int x=0,int y=0):ord(x),val(y){}
    bool operator < (const Operation& rhs) const { return ord<rhs.ord; }
}p[N*2];
typedef Operation Node;
Node q[N];
bool cmp(Node x,Node y) {return x.val<y.val;}
int main() {
    scanf("%d%d",&n,&m);
    Init(root[0],1,n);
    for(int i=1;i<=n;i++) {
        int l,r,pri;
        scanf("%d%d%d",&l,&r,&pri);
        p[i]=Operation(l,pri);
        p[i+n]=Operation(r+1,-pri);
        q[i]=Node(i,pri);
    }
    sort(q+1,q+1+n,cmp);
    for(int i=1;i<=n;i++) {
        int cach;
        if(q[i].val!=q[i-1].val) cach=i;
        else cach=p[q[i-1].ord].val;
        disc[cach]=q[i].val;
        p[q[i].ord].val=cach;
        p[q[i].ord+n].val=-cach;
    }
    sort(p+1,p+1+2*n);
    LL k=1;
    for(int i=1;i<=m;i++) {
        root[i]=root[i-1];
        while(p[k].ord==i && k<=n*2) Insert(root[i],p[k++].val,1,n);
    }
    for(int i=1;i<=m;i++) {
        int x,a,b,c;
        scanf("%d%d%d%d",&x,&a,&b,&c);
        k=1+(a*ans+b)%c;
        printf("%lld\n",ans=Query(root[x],k,1,n));
    }
    return 0;
}

第k小怎么查？和Treap差不多啦