洛谷主席模板：任务查询系统

向右看齐 2023-06-01 06:14 7阅读 0赞

## 题目描述 ##

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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行，每行一个整数，表示查询结果。

在教师听着课，写了一上午没有过，回到宿舍听着歌，就A了。神奇

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=210000;
    struct Node{int ls,rs,num;ll v;}t[M*40];//主席树
    struct node{int l,r,v;}d[M];
    int n,m,b[M],cnt,rot[M];
    vector<int> G[M];
    void build(int &k,int l,int r){
        k=++cnt; t[k].num=t[k].v=t[k].ls=t[k].rs=0;
        if(l==r)return;
        int mid=l+r>>1;
        build(t[k].ls,l,mid);
        build(t[k].rs,mid+1,r);
    }
    void update(int pre,int &k,int l,int r,int in,int type){
        k=++cnt;t[k]=t[pre];
        t[k].num+=type;t[k].v+=b[in]*type;
        if(l==r)return ;
        int mid=(l+r)>>1;
        if(in<=mid)update(t[pre].ls,t[k].ls,l,mid,in,type);
        else update(t[pre].rs,t[k].rs,mid+1,r,in,type);
    }
    ll ask(int k,int num,int l,int r){
        if(t[k].num<=num)return t[k].v;
        if(l==r) return num*b[l];
        int mid=(l+r)>>1;
        if(t[t[k].ls].num>=num)return ask(t[k].ls,num,l,mid);
        return  ask(t[k].rs,num-t[t[k].ls].num,mid+1,r)+t[t[k].ls].v;
    }
    int main(){
        scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].v),b[i]=d[i].v;
        sort(b+1,b+m+1);
        int tott=1;
        for(int i=2;i<=m;i++)if(b[i]!=b[i-1])b[++tott]=b[i];b[0]=tott;
    
        for(int i=1;i<=m;i++) {
            d[i].v=lower_bound(b+1,b+b[0]+1,d[i].v)-b;
            G[d[i].l].push_back(d[i].v);
            G[d[i].r+1].push_back(-d[i].v);
        }
        build(rot[0],1,b[0]);
        for(int i=1;i<=n;i++){
            if(G[i].size()==0){
                rot[i]=rot[i-1];
                continue;
            }
            update(rot[i-1],rot[i],1,b[0],abs(G[i][0]),G[i][0]<0?-1:1);
            for(int j=1;j<G[i].size();j++)update(rot[i],rot[i],1,b[0],abs(G[i][j]),G[i][j]<0?-1:1);
        }
        ll pre=1,a,b1,c,x,k;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld%lld",&x,&a,&b1,&c);
            k=1+(a*pre+b1)%c;
            pre=ask(rot[x],k,1,b[0]);
            printf("%lld\n",pre);
        }
        return 0;
    }