[luogu3168]:[CQOI2015]任务查询系统

Description

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


Solution

这道题卡了我一下午!!!
首先把任务优先级离散化。
以时间为根,任务优先级为区间建一棵主席树。
差分的思想把每一个区间拆成两个修改的操作,然后在树上乱搞就行了…qwq

主要是第一次遇到可以多次修改的操作orzzzz


Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define re register int
#define ll long long
using namespace std;

inline int abs(int x){
    return x>0?x:-x;
}

inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}

const int N=1e5+5;
const int inf=1e7;
ll ans=1;
int n,m;
struct Segment_Tree{
    int size;
    ll sum;
    Segment_Tree *ls,*rs;
    Segment_Tree(Segment_Tree *x) {
        if(x==NULL){
            size=0;sum=0;ls=rs=NULL;
        }
        else {
            size=x->size;sum=x->sum;ls=x->ls;rs=x->rs;
        }
    }
}*root[N];
int b[N];
typedef Segment_Tree Node;

inline Node *build(int l,int r){
    Node *cur=new Node(NULL);
    if(l<r){
        int mid=(l+r)>>1;
        cur->ls=build(l,mid);
        cur->rs=build(mid+1,r);
    }
    return cur;
}

inline void insert(Node *&cur,int l,int r,int f,int p){
    Node *tmp=cur;
    cur=new Node(tmp);
    cur->size+=f;
    cur->sum+=(ll)f*b[p];
    if(l<r){
        int mid=(l+r)>>1;
        if(p<=mid)insert(cur->ls,l,mid,f,p);
        else insert(cur->rs,mid+1,r,f,p);
    }
}

inline ll query(Node *o,int l,int r,int k){
    if(k>o->size)return o->sum;
    if(l==r)return ((o->sum)/(o->size))*k;
    int mid=(l+r)>>1;
    if(o->ls!=NULL){
        if(o->ls->size>=k)return query(o->ls,l,mid,k);
        return o->ls->sum+query(o->rs,mid+1,r,k-o->ls->size);
    }
    return query(o->rs,mid+1,r,k);
}

struct data{
    int id,val,tag;
    data(int i=0,int v=0,int t=0):id(i),val(v),tag(t){}
    bool operator <(const data &o)const {
        return val<o.val;
    }
}p[N<<1],q[N];

inline bool cmp(data x,data y){
    return x.id<y.id;
}

inline void print(){
    printf("---------------------------\n");
}

int main(){
    m=read(),n=read();
    root[0]=build(1,m);
    for(re i=1;i<=m;i++){
        int l=read(),r=read(),v=read();
        p[i]=data(l,v,1);
        p[i+m]=data(r+1,v,-1);
        q[i]=data(i,v,1);
    /*  print();
        printf("%d %d %d\n",p[i].id,p[i].val,p[i].tag);
        printf("%d %d %d\n",p[i+m].id,p[i+m].val,p[i+m].tag);
        print();*/
    }

    sort(q+1,q+m+1);
    for(re i=1;i<=m;i++){
        int tmp;
        if(q[i].val!=q[i-1].val)tmp=i;
        else tmp=p[q[i-1].id].val;
        b[tmp]=q[i].val;
        p[q[i].id].val=tmp;
        p[q[i].id+n].val=tmp;
    }
    sort(p+1,p+2*m+1,cmp);
    int now=0;
    //print();
    for(re i=1;i<=n;i++){
        root[i]=root[i-1];
        while(now!=2*m&&p[now+1].id==i){
            now++;
            //printf("%d %d %d\n",p[now].id,p[now].val,p[now].tag);
            /*int rk=lower_bound(b+1,b+2*m+1,p[now].val)-b;
            printf("%d %d\n",b[rk],p[now].val);
            print();*/
            insert(root[i],1,m,p[now].tag,p[now].val);
        }
    }
    while(n--){
        int X=read(),A=read(),B=read(),C=read();
        int kth=1+(A*ans+B)%C;
        printf("%lld\n",ans=query(root[X],1,m,kth));
    }
    //for(re i=1;i<=3;i++)
    //  printf("%d\n",root[i]->sum);
    return 0;
}