首页 > > 程序设计 > C/C++ >

bzoj3932 [ CQOI2015 ] --可持久化线段树

2018-06-27 09:59:19来源：未知阅读 ()

题目大意：

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的

任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行

），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向

查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个

）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先

级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

思路：

先将优先值离散，然后对每个时间建一棵记录当前时间正在运行的优先值为l~r的任务的个数、优先值之和的线段树，显然可以用主席树优化。一个从s到t的任务可以看成在s时间发生，在t+1时间结束，于是一个任务只需要在s和t+1更新。

对于查找，判断当前要找的k和左子树任务个数的大小关系，如果k大，查询右子树，否则查询左子树。注意当l==r时返回要注意k的值。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100001
#define ll long long
inline void Read(long long& x){
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar());
}
inline void Read(int& x){
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar());
}
vector<int>a1[N],a2[N];
struct node{
    int l,r,s;
    ll w;
}c[N*80];
struct gj{
    int x,y,z;
}b[N];
struct ls{
    int w,f;
}a[N];
int i,j,Rt[N],k,Num,n,m,M;
ll Last=1,w2[N],x,y,z;
inline void Update(int& Node,int l,int r,int x,int y){
    c[++Num]=c[Node];Node=Num;
    c[Node].w+=w2[x]*y;c[Node].s+=y;
    if(l==r)return;
    int Mid=(l+r)>>1;
    if(x<=Mid)Update(c[Node].l,l,Mid,x,y);else Update(c[Node].r,Mid+1,r,x,y);
}
inline ll Query(int Node,int l,int r,int x){
    if(l==r)return c[Node].w/c[Node].s*x;
    int Mid=(l+r)>>1;
    if(c[c[Node].l].s>x)return Query(c[Node].l,l,Mid,x);else if(c[c[Node].l].s==x)return c[c[Node].l].w;else return Query(c[Node].r,Mid+1,r,x-c[c[Node].l].s)+c[c[Node].l].w;
}
inline bool Cmp(ls a,ls b){
    return a.w<b.w;
}
int main()
{
    Read(m);Read(n);
    for(i=1;i<=m;i++)Read(b[i].x),Read(b[i].y),Read(b[i].z),a[i].w=b[i].z,a[i].f=i;
    sort(a+1,a+m+1,Cmp);
    for(i=1;i<=m;i++)if(a[i].w==a[i-1].w)b[a[i].f].z=M;else b[a[i].f].z=++M,w2[M]=a[i].w;
    for(i=1;i<=m;i++){
        a1[b[i].x].push_back(b[i].z);a2[b[i].y+1].push_back(b[i].z);
    }
    for(i=1;i<=n;i++){
        Rt[i]=Rt[i-1];
        for(j=0;j<a1[i].size();j++)Update(Rt[i],1,M,a1[i][j],1);
        for(j=0;j<a2[i].size();j++)Update(Rt[i],1,M,a2[i][j],-1);
    }
    for(i=1;i<=n;i++){
        Read(k);Read(x);Read(y);Read(z);
        x=((x*Last+y)%z)+1;
        if(c[Rt[k]].s<=x)Last=c[Rt[k]].w;else Last=Query(Rt[k],1,M,x);
        printf("%lld\n",Last);
    }
    return 0;
}