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

Emplace · 2025-11-30 16:51:21 · 个人记录

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

思路

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

前缀和记为 sum_{i,j} 为第 i 个块前 j 个下标（注意不是数）有多少个。

然后查询时，我们就直接枚举每一块，加上这个块有几个数下标在 l 到 r 之间。即设这个块是第 i 个块，则加上 sum_{i,r}-sum_{i,l-1}。

如果加上一个块加上后大于等于了 k。则直接枚举这一个块，一个一个加上知道有了 k 个。最后一个加的数即为答案。

时间复杂度为 O(n\sqrt{n}+m\sqrt{n})。

代码

#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;
}