[BZOJ3932][CQOI2015]任务查询系统(差分+主席树)

题面

分析

对于一个区间修改(s,e,v),我们可以将它差分，这样就变成了单点修改s和e+1（s插入，t+1删除）

我们用主席树维护差分数组的前缀和，第i棵主席树维护区间[1,i]之间的所有差分值

那么查询我们直接在第i棵主席树里查第k大即可

注意:

1.主席树里面要维护两个值，一个是值落在区间[l,r]内的树的个数cnt，一个是这cnt个数的和

2.注意有多个数相同的情况，查询到叶子节点[l,l]之后，不能直接返回sum,而是应该返回k*b[l],其中b[l]是l离散化之前的值

这里有一组hack数据

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define maxn 300005

#define maxlogn 21

using namespace std;

int m,n;

vector<int>d[maxn];

int b[maxn];

int sz;

struct node{

#ifdef DEBUG

	int l;

	int r;

#endif

	int ls;

	int rs;

	int cnt;

	long long sum;

}tree[2*maxn*maxlogn];

int root[maxn*2];

int ptr;

void push_up(int pos){

	tree[pos].cnt=tree[tree[pos].ls].cnt+tree[tree[pos].rs].cnt;

	tree[pos].sum=tree[tree[pos].ls].sum+tree[tree[pos].rs].sum;

}

void update(int &pos,int last,int upos,int uval,int flag,int l,int r){

	pos=++ptr;

	tree[pos]=tree[last];

#ifdef DEBUG

	tree[pos].l=l;

	tree[pos].r=r;

#endif

	if(l==r){

		tree[pos].cnt+=flag;

		tree[pos].sum+=uval*flag;

		return;

	}

	int mid=(l+r)>>1;

	if(upos<=mid) update(tree[pos].ls,tree[last].ls,upos,uval,flag,l,mid);

	else update(tree[pos].rs,tree[last].rs,upos,uval,flag,mid+1,r);

	push_up(pos);

}

long long query(int ql,int qr,int qk,int l,int r){

	if(l==r){

		//注意多组数据相同的情况，必须要用k*值，不能用sum

		//见最下方hack数据

		return b[l]*qk;

	}

	int mid=(l+r)>>1;

	int lcnt=tree[tree[qr].ls].cnt-tree[tree[ql].ls].cnt;

	if(qk<=lcnt) return query(tree[ql].ls,tree[qr].ls,qk,l,mid);

	else return tree[tree[qr].ls].sum-tree[tree[ql].ls].sum+query(tree[ql].rs,tree[qr].rs,qk-lcnt,mid+1,r);

}

int main(){

	int s,e,v;

	long long xx,aa,bb,cc;

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

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

		scanf("%d %d %d",&s,&e,&v);

		d[s].push_back(v);

		d[e+1].push_back(-v);

		b[++sz]=v;

	}

	sort(b+1,b+1+sz);

	sz=unique(b+1,b+1+sz)-b-1;

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

		root[i]=root[i-1];

		for(int j=0;j<d[i].size();j++){

			int val=d[i][j];//正数代表插入，负数代表删除

			int disval=lower_bound(b+1,b+1+sz,abs(val))-b;

			if(val<0) update(root[i],root[i],disval,abs(val),-1,1,sz);

			else update(root[i],root[i],disval,abs(val),1,1,sz);

		}

	}

	long long ans=1;

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

		scanf("%lld %lld %lld %lld",&xx,&aa,&bb,&cc);

		long long k=1+(aa*ans+bb)%cc;

		if(k>tree[root[xx]].cnt) ans=tree[root[xx]].sum;

		else ans=query(root[0],root[xx],k,1,sz);

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

	}

}

巴特西

[BZOJ3932][CQOI2015]任务查询系统(差分+主席树)

题面

分析

代码

最新文章

热门文章