欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[CQOI2015]任务查询系统

程序员文章站 2024-03-20 12:43:04
...

3932: [CQOI2015]任务查询系统

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 4329  Solved: 1428
[Submit][Status][Discuss]

Description

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

Input

输入文件第一行包含两个空格分开的正整数m和n,分别表示任务总数和时间范围。接下来m行,每行包含三个空格
分开的正整数Si、Ei和Pi(Si≤Ei),描述一个任务。接下来n行,每行包含四个空格分开的整数Xi、Ai、Bi和Ci,
描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果,
对于第一次查询,Pre=1。
 
 

Output

输出共n行,每行一个整数,表示查询结果。
 

Sample Input

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

Sample Output

2
8
11

优秀的解法当然是主席树了

初始值的时候加入 结束时+1删除 然后区间求和就行了

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pii pair<ll,int>
const int MAXN=1e5+10;
using namespace std;
typedef struct node{
    int l,r,num;ll sum;
}node;
node d[45*MAXN];
int rt[MAXN];
vector<ll>vec;int cnt;
void update(int &x,int y,int l,int r,int t,int flag){
    x=++cnt;d[x]=d[y];
    if(flag) d[x].num++,d[x].sum+=vec[t-1];
    else d[x].num--,d[x].sum-=vec[t-1];
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(t<=mid) update(d[x].l,d[y].l,l,mid,t,flag);
    else update(d[x].r,d[y].r,mid+1,r,t,flag);
}
ll sum;
void querty(int x,int l,int r,int k){
    //cout<<l<<" "<<r<<" "<<d[x].sum<<endl;
    if(l==r) {sum+=vec[l-1]*k;return ;}
    int mid=(l+r)>>1;
    if(d[d[x].l].num>=k) querty(d[x].l,l,mid,k);
    else sum+=d[d[x].l].sum,querty(d[x].r,mid+1,r,k-d[d[x].l].num);
}
vector<pii>vv[MAXN];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    int l,r;ll x;
    for(int i=1;i<=n;i++){
        scanf("%d%d%lld",&l,&r,&x);
        vv[l].push_back(make_pair(x,1));
        vv[r+1].push_back(make_pair(x,0));
        vec.push_back(x);
    }
    sort(vec.begin(),vec.end());
    int t=unique(vec.begin(),vec.end())-vec.begin();
    for(int i=0;i<=n+1;i++){
        if(i) rt[i]=rt[i-1];
        for(int j=0;j<vv[i].size();j++){
            vv[i][j].f=lower_bound(vec.begin(),vec.begin()+t,vv[i][j].f)-vec.begin()+1;
            update(rt[i],rt[i],1,t,vv[i][j].f,vv[i][j].s);}
    }
    ll a,b,c;ll Lans=1;ll k;
    for(int i=1;i<=m;i++){
        scanf("%d%lld%lld%lld",&x,&a,&b,&c);
        k=1+(a*Lans+b)%c;
        if(d[rt[x]].num<=k) Lans=d[rt[x]].sum;
        else sum=0,querty(rt[x],1,t,k),Lans=sum;
        printf("%lld\n",Lans);
    }
    return 0;
}

 撸一发可持久化treap 第一次写这个 调了很久  最后发现wa点在查询的时候 写挂了!!!一直以为是持久化的地方写错了!!!

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pii pair<ll,int>
const int MAXN=1e5+10;
using namespace std;
int ch[MAXN*100][2],size[MAXN*100],fst[MAXN*100];
int s[MAXN*100],cnt1;
ll sum[MAXN*100],key[MAXN*100];
int rt[MAXN],cnt;
vector<pii>vv[MAXN];
int newnode(ll vul){
    int x;
    if(cnt1) x=s[cnt1--];
    else x=++cnt;
    ch[x][0]=ch[x][1]=0;size[x]=1;key[x]=sum[x]=vul;fst[x]=rand();
    return x;
}
int copynode(int y){
    int x;
    if(cnt1) x=s[cnt1--];
    else x=++cnt;
    fst[x]=fst[y];
    ch[x][0]=ch[y][0];ch[x][1]=ch[y][1];key[x]=key[y];sum[x]=sum[y];size[x]=size[y];
    return x;
}
void up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];}
int merge(int x,int y){
    if(!x) return y;
    if(!y) return x;
    int r;
    if(fst[x]<=fst[y]){
        r=copynode(x);
        ch[r][1]=merge(ch[x][1],y);
        up(r);
        return r;
    }
    else{
        r=copynode(y);
        ch[r][0]=merge(x,ch[y][0]);
        up(r);
        return r;
    }
}
pii split(int x,int k){
    if(!x) return make_pair(0,0);
    pii y;int r;r=copynode(x);
    if(size[ch[r][0]]>=k){
        y=split(ch[r][0],k);
        ch[r][0]=y.s;
        up(r);
        y.s=r;
    }
    else{
        y=split(ch[r][1],k-size[ch[r][0]]-1);
        //r=copynode(x);
        ch[r][1]=y.f;
        up(r);
        y.f=r;
    }
    return y;
}
int ans;
void find1(int x,ll vul){
    if(!x) return ;
    if(key[x]<=vul) ans+=(size[ch[x][0]]+1),find1(ch[x][1],vul);
    else find1(ch[x][0],vul);
}
void insert(int &x,ll vul){
    ans=0;find1(x,vul);
    pii y1=split(x,ans);
    int t=newnode(vul);
    x=merge(merge(y1.f,t),y1.s);
}
void erase(int &x,int vul){
    ans=0;find1(x,vul);
    pii y1=split(x,ans-1);
    pii y2=split(y1.s,1);
    s[++cnt1]=y2.f;
    x=merge(y1.f,y2.s);
}
ll ans1;
void querty(int x,int k){
    if(!x || !k) return ;
    if(size[ch[x][0]]+1==k) {ans1+=(key[x]+sum[ch[x][0]]);return ;}
    else if(size[ch[x][0]]>=k) querty(ch[x][0],k);
    else ans1+=(key[x]+sum[ch[x][0]]),querty(ch[x][1],k-size[ch[x][0]]-1);
}
int main(){
    cnt=cnt1=0;
    int n,m;scanf("%d%d",&n,&m);
    int l,r;ll x;
    for(int i=1;i<=n;i++){
        scanf("%d%d%lld",&l,&r,&x);
        vv[l].push_back(make_pair(x,1));
        vv[r+1].push_back(make_pair(x,0));
    }
    for(int i=0;i<=n+1;i++){
        if(i) rt[i]=rt[i-1];
        for(int j=0;j<vv[i].size();j++){
            if(vv[i][j].s) insert(rt[i],vv[i][j].f);
            else erase(rt[i],vv[i][j].f);
    }
    }
    //for(int i=1;i<=n;i++) debug(rt[i]);
    ll a,b,c;ll Lans=1;ll k;
    for(int i=1;i<=m;i++){
        scanf("%d%lld%lld%lld",&x,&a,&b,&c);
        k=1+(a*Lans+b)%c;
        if(size[rt[x]]<=k) Lans=sum[rt[x]];
        else ans1=0,querty(rt[x],k),Lans=ans1;
        printf("%lld\n",Lans);
    }
    return 0;
}