BZOJ-3932: [CQOI2015]任务查询系统

[文章目录]

Description

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

强制在线,将优先级离散化,然后按照时间建主席树,维护sum和siz,注意到叶子节点需要单独计算sum。内存回收的话由于可能涉及到前面的时间,所以不能回收。空间复杂度n*logn。

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
vector <int> v[N<<1];
int n,m,a[N],c[N],tot;
int getid(int x)
{
    int l=1,r=tot+1,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(c[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
ll sum[N*50]; int ls[N*50],rs[N*50],siz[N*50],cnt,root[N];
void update(int l,int r,int z,int &x,int y,int w)
{
    x=++cnt; sum[x]=sum[y]+w; siz[x]=siz[y]+((w>0)?1:-1);
    if(l==r) return ;
    int mid=l+r>>1;
    if(z<=mid) rs[x]=rs[y],update(l,mid,z,ls[x],ls[y],w);
    else ls[x]=ls[y],update(mid+1,r,z,rs[x],rs[y],w);
}
void build()
{
    for(int i=1;i<=m;i++)
    {
        root[i]=root[i-1];
        for(int j=0;j<v[i].size();j++)
            update(1,tot,getid(v[i][j]),root[i],root[i],v[i][j]);
        for(int j=0;j<v[i+m].size();j++)
            update(1,tot,getid(v[i+m][j]),root[i],root[i],-v[i+m][j]);
    }
}
ll query(int l,int r,int x,int y)
{
    if(!y) return 0;
    if(siz[x]<=y) return sum[x];
    if(l==r){return 1ll*c[l]*y;}
    int mid=l+r>>1;
    if(siz[ls[x]]<=y) return sum[ls[x]]+query(mid+1,r,rs[x],y-siz[ls[x]]);
    else return query(l,mid,ls[x],y);
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,x,y,z;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        a[i]=z; v[x].push_back(z); v[y+m+1].push_back(z);
    }
    sort(a+1,a+n+1); tot=1; c[1]=a[1];
    for(i=2;i<=n;i++) if(a[i]!=a[i-1]) c[++tot]=a[i];
    build();
    ll pre=1,ai,bi,ci;
    while(m--)
    {
        scanf("%d%lld%lld%lld",&x,&ai,&bi,&ci);
        ai=(ai%ci*(pre%ci)%ci+bi)%ci+1;
        printf("%lld\n",pre=query(1,tot,root[x],ai));
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注