lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。