[CQOI2015]任务查询系统

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;
}