[bzoj3932][CQOI2015][任务查询系统] （主席树）

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

Sample Output

HINT

样例解释

K1 = (1*1+3)%2+1 = 1

K2 = (1*2+3)%4+1 = 2

K3 = (2*8+4)%3+1 = 3

对于100%的数据，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi为1到n的一个排列

Solution

对每个按时间排序，插入到对时间点建以任务优先级为区间的主席树，处理一个记录和的键值，以及一个处理数量的键值就可以做了

注意要开long long，而且空间不能只开n*log2(len)大小的，至少n*60

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 100010

#define ll long long

#define INF 10000000

#define mid ((x>>1)+(y>>1)+(x&y&1))

using namespace std;

inline ll Rin(){

    ll x=,c=getchar(),f=;

    for(;c<||c>;c=getchar())

        if(!(c^))f=-;

    for(;c>&&c<;c=getchar())

        x=(x<<)+(x<<)+c-;

    return x*f;

}

struct Seg{

    ll sum;

    int sin,ls,rs;

}key[N*];

vector<int>L[N],R[N];

int n,m,rt[N],tot,mn=INF,mx,sign,mark[N*];

void newnode(int &pr,int pl){

    key[pr=++tot]=key[pl];

    mark[pr]=sign;

}

void modify(int &pr,int pl,int x,int y,int k,int d){

    if(mark[pl]^sign)

        newnode(pr,pl);

    key[pr].sin+=d;

    key[pr].sum+=k*d;

    if(!(x^y))return;

    if(k<=mid)modify(key[pr].ls,key[pl].ls,x,mid,k,d);

    else modify(key[pr].rs,key[pl].rs,mid+,y,k,d);

}

ll query(int p,int x,int y,int k){

    if(!(x^y))return (ll)x*k;

    if(key[key[p].ls].sin>=k)return query(key[p].ls,x,mid,k);

    return key[key[p].ls].sum+query(key[p].rs,mid+,y,k-key[key[p].ls].sin);

}

int main(){

    n=Rin(),m=Rin();

    for(int i=;i<=n;i++){

        int x=Rin(),y=Rin(),z=Rin();

        L[x].push_back(z);

        R[y].push_back(z);

        mn=min(mn,x);

        mx=max(mx,y);

    }

    for(int i=mn;i<=mx;i++){

        newnode(rt[i],rt[i-]);sign++;

        for(int j=;j<L[i].size();j++)

            modify(rt[i],rt[i],,INF,L[i][j],);

        for(int j=;j<R[i-].size();j++)

            modify(rt[i],rt[i],,INF,R[i-][j],-);

    }

    ll a,b,c,ans=;

    while(m--){

        int x=Rin();

        a=Rin(),b=Rin(),c=Rin();

        int k=(int)+(a*ans+b)%c;

        if(key[rt[x]].sin<=k)

            printf("%lld\n",ans=key[rt[x]].sum);

        else

            printf("%lld\n",ans=query(rt[x],,INF,k));

    }

    return ;

}

秒客网