题解：P3834 【模板】可持久化线段树 2

这道题竟然没有纯分块题解，所以让我来写一篇。

思路

这道题目我们可以对原数组进行排序，再对每一个块记一个前缀和。

前缀和记为

sum_{i,j}

为第

i

个块前

j

个下标（注意不是数）有多少个。

然后查询时，我们就直接枚举每一块，加上这个块有几个数下标在

l

到

r

之间。即设这个块是第

i

个块，则加上

sum_{i,r}-sum_{i,l-1}

。

如果加上一个块加上后大于等于了

k

。则直接枚举这一个块，一个一个加上知道有了

k

个。最后一个加的数即为答案。

时间复杂度为

O(n\sqrt{n}+m\sqrt{n})

。

代码

CPP

#include<bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;
int n,m,sum[449][200001],idk[200001],lk[448],rk[448],len,kuai;
struct node{
	int x,id;
}a[200001];
bool cmp(node s1,node s2){
	return s1.x<s2.x;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x,a[i].id=i;;
	}
	sort(a+1,a+1+n,cmp);
	int len=sqrt(n),kuai=sqrt(n);
	if(kuai*kuai!=n) kuai++,len++;
	for(int i=1;i<=kuai;i++){
		lk[i]=rk[i-1]+1,rk[i]=min(n,lk[i]+len-1);
		for(int j=lk[i];j<=rk[i];j++){
			idk[j]=i;
			sum[i][a[j].id]++;
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
		}
	}
	while(m--){
		int l,r,k;
		cin>>l>>r>>k;
		int cnt=0,ans=0;
		for(int i=1;i<=kuai;i++){
			if(cnt+sum[i][r]-sum[i][l-1]<k){
				cnt+=sum[i][r]-sum[i][l-1];
				continue;
			}
			for(int j=lk[i];j<=rk[i];j++){
				if(a[j].id>=l&&a[j].id<=r) cnt++;
				if(cnt==k){
					ans=a[j].x;
					break;
				}
			}
			break;
		}
		cout<<ans<<endl;
	}
	return 0;
}

题解：P3834 【模板】可持久化线段树 2

文章操作

思路

代码

相关推荐

评论

题解：P3834 【模板】可持久化线段树 2