P3332 - K大数查询题解

本文主要是介绍P3332 - K大数查询题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

好像是经典题（？），那就写一波题解罢。

BIT 套动态开点线段树

考虑查询，集合里的元素每个有两个指标：所在集合编号和自身权值，那么查询容易想到二分，二分的 chk 其实就是个二维数点。是动态的（实际上这个修改比动态加点强），二分的 chk 这玩意可以看作半在线，就暂时考虑在线动态维护二维数点了吧。

那就考虑树套树，自然的想法是外层维护集合编号，内层维护权值。这样带来两个问题：修改操作相当于 \(1\times ?\) 矩形增加，不会做，\(?\times 1\) 就会做了（就找到那一列在所在内层线段树上区修，之于外层 BIT 来说是单点修改）；以及复杂度是 3log 的，感觉要 2log 才能过。

其实~~让孩子搞基~~把内外层维护的 swap 一下（就跟 wjz 出的那个 taking a walk 一样的套路（那题题解鸽了快半年了，既然这样就永远鸽下去吧！））可以解决所有问题。前者不 solve 自 solve，后者的话，由于二分的是权值，而外层维护权值，所以可以在外层 BIT 上倍增，把 log 平行化掉。

这个方法啥都好，就是空间是 2log 的。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x){return x&-x;}
const int N=100010,LOG_N=18;
int n,qu;
int sz;
struct node{signed lson,rson,lz;int cnt;}nd[N*200];
#define lson(p) nd[p].lson
#define rson(p) nd[p].rson
#define lz(p) nd[p].lz
#define cnt(p) nd[p].cnt
int nwnd(){return nd[++sz]=node({0,0,0,0}),sz;}
struct segtree{
	int root;
	void init(){root=nwnd();}
	void sprdwn(int p,int l,int r){
		if(lz(p)){
			if(!lson(p))lson(p)=nwnd();if(!rson(p))rson(p)=nwnd();
			int mid=l+r>>1;
			cnt(lson(p))+=1ll*lz(p)*(mid-l+1),lz(lson(p))+=lz(p);
			cnt(rson(p))+=1ll*lz(p)*(r-mid),lz(rson(p))+=lz(p);
			lz(p)=0;
		}
	}
	void sprup(int p){cnt(p)=cnt(lson(p))+cnt(rson(p));}
	void add(int l,int r,int p=-1,int tl=1,int tr=n){~p||(p=root);
		if(l<=tl&&r>=tr)return cnt(p)+=tr-tl+1,lz(p)++,void();
		sprdwn(p,tl,tr);
		int mid=tl+tr>>1;
		if(l<=mid){
			if(!lson(p))lson(p)=nwnd();
			add(l,r,lson(p),tl,mid);
		}
		if(r>mid){
			if(!rson(p))rson(p)=nwnd();
			add(l,r,rson(p),mid+1,tr);
		}
		sprup(p);
	}
	int _cnt(int l,int r,int p=-1,int tl=1,int tr=n){~p||(p=root);
		if(l<=tl&&r>=tr)return cnt(p);
		sprdwn(p,tl,tr);
		int mid=tl+tr>>1,res=0;
		if(l<=mid)res+=_cnt(l,r,lson(p),tl,mid);
		if(r>mid)res+=_cnt(l,r,rson(p),mid+1,tr);
		return res;
	}
};
struct bitree{
	segtree cnt[N];
	void init(){
		for(int i=1;i<=2*n+1;i++)cnt[i].init();
	}
	void add(int x,int l,int r){
		while(x<=2*n+1)cnt[x].add(l,r),x+=lowbit(x);
	}
	int fd(int l,int r,int x){
		int res=0,_cnt=0;
		for(int i=LOG_N-1;~i;i--)if(res+(1<<i)<=2*n+1&&_cnt+cnt[res+(1<<i)]._cnt(l,r)<x)
			res+=1<<i,_cnt+=cnt[res]._cnt(l,r);
		return res+1;
	}
}bit;
signed main(){
//	cout<<sizeof(nd[0]);
	cin>>n>>qu;
	bit.init();
	while(qu--){
		int tp,l,r,x;
		scanf("%lld%lld%lld%lld",&tp,&l,&r,&x);
		if(tp==1)bit.add(-x+n+1,l,r);
		else printf("%lld\n",-(bit.fd(l,r,x)-n-1));
	}
	return 0;
}

整体二分

由于允许离线，考虑整体二分。

二分区间 \([l,r]\) 的时候，我们 chk 要看的事情就是对每个询问 \(([l_0,r_0],x)\) 看 \([l_0,r_0]\) 内小于等于 \(mid\) 的个数是否小于等于 \(x\)。我们需要动态求这玩意，这其实就很简单了：按顺序扫所有的 query，如果是修改 \(([l_0,r_0],x)\) 并且 \(x\leq mid\) 那么它有贡献，区间 \([l_0,r_0]\) 加；如果是查询那就线段树里面查就可以了。

但目前有个问题：\(x\) 特别小的修改有可能在很多很多整体二分的子问题里面贡献非零，这样它一路走的路径就不是一条直链！这里涉及二分的一个常用技巧：当前层如果某个询问 \(([l_0,r_0],x)\) 查出来个数是 \(y\) 且 \(x>y\)，那 duck 令 \(x\gets x-y\)，这样以后就不用考虑前面的修改的贡献了。那这样每层处理完后，不光查询会被分到左右两部分中的一部分（这个在任何整体二分中都恒成立），修改也是被分到恰好（或者说最多？）一部分，没被分到就是贡献必定为 \(0\)。

这样一来每个整体二分的子问题就是关于被分到的 query 个数（查询 + 修改）的 1log，总复杂度就是 2log。注意每次不能给线段树暴力 init（那样复杂度就加上总值域，就被破坏了），需要每次处理完加上负值抵消掉。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N=100010;
int n,qu;
struct query{int tp,l,r,x,id;}qry[N];
struct segtree{
	struct node{int cnt,lz;}nd[N<<2];
	#define cnt(p) nd[p].cnt
	#define lz(p) nd[p].lz
	void init(){memset(nd,0,sizeof(nd));}
	void sprdwn(int p,int l,int r){
		if(lz(p)){
			int mid=l+r>>1;
			cnt(p<<1)+=1ll*lz(p)*(mid-l+1),lz(p<<1)+=lz(p);
			cnt(p<<1|1)+=1ll*lz(p)*(r-mid),lz(p<<1|1)+=lz(p);
			lz(p)=0;
		}
	}
	void sprup(int p){cnt(p)=cnt(p<<1)+cnt(p<<1|1);}
	void add(int l,int r,int v,int p=1,int tl=1,int tr=n){
		if(l<=tl&&r>=tr)return cnt(p)+=v*(tr-tl+1),lz(p)+=v,void();
		sprdwn(p,tl,tr);
		int mid=tl+tr>>1;
		if(l<=mid)add(l,r,v,p<<1,tl,mid);
		if(r>mid)add(l,r,v,p<<1|1,mid+1,tr);
		sprup(p);
	}
	int _cnt(int l,int r,int p=1,int tl=1,int tr=n){
		if(l<=tl&&r>=tr)return cnt(p);
		sprdwn(p,tl,tr);
		int mid=tl+tr>>1,res=0;
		if(l<=mid)res+=_cnt(l,r,p<<1,tl,mid);
		if(r>mid)res+=_cnt(l,r,p<<1|1,mid+1,tr);
		return res;
	}
}segt;
int ans[N];
void solve(int l,int r,vector<query> v){
	if(l==r){
		for(int i=0;i<v.size();i++){
			int tp=v[i].tp,id=v[i].id;
			if(tp==2)ans[id]=l;
		}
		return;
	}
	int mid=l+r>>1;
	vector<query> lft,rit;
	for(int i=0;i<v.size();i++){
		int tp=v[i].tp,l=v[i].l,r=v[i].r,x=v[i].x;
		if(tp==1){
			if(x<=mid)segt.add(l,r,1),lft.pb(v[i]);
			else rit.pb(v[i]);
		}
		else{
			int fd=segt._cnt(l,r);
			if(x<=fd)lft.pb(v[i]);
			else v[i].x-=fd,rit.pb(v[i]);
		}
	}
	for(int i=0;i<v.size();i++){
		int tp=v[i].tp,l=v[i].l,r=v[i].r,x=v[i].x,id=v[i].id;
		if(tp==1&&x<=mid)segt.add(l,r,-1);
	}
	solve(l,mid,lft),solve(mid+1,r,rit);
}
signed main(){
	cin>>n>>qu;
	for(int i=1;i<=qu;i++)scanf("%lld%lld%lld%lld",&qry[i].tp,&qry[i].l,&qry[i].r,&qry[i].x),qry[i].id=i;
	vector<query> v;
	for(int i=1;i<=qu;i++)qry[i].tp==1&&(qry[i].x*=-1),v.pb(qry[i]);
	segt.init();
	solve(-n,n,v);
	for(int i=1;i<=qu;i++)if(qry[i].tp==2)printf("%lld\n",-ans[i]);
	return 0;
}

二进制分组

上面的上面那个在线动态二维数点考虑一波二进制分组 + 主席树。如果主席树的历史版本编号是权值的话，那照样是只能 3log 的；如果颠倒过来的话，依然可以在一棵虚空中的线段树（其实就是只有位置信息）上二分，每次把 2 倍 log 棵线段树的该位置加（减）起来，就相当于 log 个静态区间第 k 大并起来做一样，是可以做到 2log 的。但好像比较难写，就不写了 2333。

这篇关于P3332 - K大数查询题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程