BZOJ_3932_[CQOI2015]任务查询系统

BZOJ_3932_[CQOI2015]任务查询系统_主席树

题意：

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

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

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

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

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

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

分析：

对每秒的状态开一棵线段树

结点保存size和sum

主席树上差分直接搞

注意优先级最小的k个最后可能小于叶子节点的size

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 800050

#define LL long long

const int maxn=10000000;

int t[N*20],ls[N*20],rs[N*20],n,m,cnt;

int head[N],to[N<<1],nxt[N<<1],val[N<<1],tot=1,root[N];

LL sum[N*20];

inline void add(int u,int v,int w){

	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;

}

void insert(int x,int &y,int l,int r,int v,int c){

	y=++tot;

	if(l==r){t[y] = t[x] + c; sum[y] = sum[x] + c * v; return ;}

	int mid=l+r>>1;

	if(v<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,v,c);

	else ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,v,c);

	t[y]=t[ls[y]]+t[rs[y]];

	sum[y]=sum[ls[y]]+sum[rs[y]];

}

LL query(int x,int l,int r,int k){

	if(l==r) return 1ll*l*min(k,t[x]);

	int mid=l+r>>1;

	if(k<=t[ls[x]])	return query(ls[x],l,mid,k);

	else return query(rs[x],mid+1,r,k-t[ls[x]]) + sum[ls[x]];

}

int qx(int x,int l,int r,int k){

	if(l==r) return l;

	int mid=l+r>>1;

	if(k<=t[ls[x]]) return qx(ls[x],l,mid,k);

	else return qx(rs[x],mid+1,r,k-t[ls[x]]);

}

int main(){

	scanf("%d%d",&n,&m);

	int i,x,y,z,j,w;

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

		scanf("%d%d%d",&x,&y,&z);

		add(x,z,1);add(y+1,z,-1);

	}

	for(i=1;i<=m;i++){

		int f=0;

		for(j=head[i];j;j=nxt[j]){

			if(!f){insert(root[i-1],root[i],1,maxn,to[j],val[j]);f=1;}

			else insert(root[i],root[i],1,maxn,to[j],val[j]);

		}

		if(!f)	root[i]=root[i-1];

	}

	LL ans=1;

	for(i=1;i<=m;i++){

		scanf("%d%d%d%d",&x,&y,&z,&w);

		y=(y*ans+z)%w+1;

		ans=query(root[x],1,maxn,y);

		printf("%lld\n",ans);

	}

}

巴特西

BZOJ_3932_[CQOI2015]任务查询系统_主席树

最新文章

热门文章