主席树题目整理

主席树题目整理

主席树题目整理

前话：由于太菜，所以开个坑整理有关主席树的题目，可能会咕咕咕。

1.P3834 【模板】可持久化线段树 2（主席树）

区间第 k k k小，转权值主席树，具体见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5,M=N*21,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
template<class T>
inline void read(T &x){ x=0;int w=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch&15);x*=w; 
}
int a[N],rt[M],b[N];
struct PST{int lx[M],rx[M],s[M],cnt;void build(int &x,int l,int r){	//建树 x=++cnt;if(l==r){return;}	int mid=(l+r)>>1;build(lx[x],l,mid),build(rx[x],mid+1,r);}void upd(int &x,int pre,int l,int r,int v){	//更新 x=++cnt,lx[x]=lx[pre],rx[x]=rx[pre],s[x]=s[pre]+1; if(l==r){return;}int mid=(l+r)>>1;if(v<=mid) upd(lx[x],lx[pre],l,mid,v);else upd(rx[x],rx[pre],mid+1,r,v);}int query(int l,int r,int u,int v,int k){	//查询. if(l>=r) return l;int cnt=s[lx[v]]-s[lx[u]];int mid=(l+r)>>1;if(cnt>=k) return query(l,mid,lx[u],lx[v],k);else return query(mid+1,r,rx[u],rx[v],k-cnt);}
}T;
int main(){int n,m;read(n),read(m);for(reg int i=1;i<=n;i++)read(a[i]),b[i]=a[i];sort(b+1,b+n+1);	//离散化. int cnt=unique(b+1,b+n+1)-b-1;T.build(rt[0],1,cnt);for(reg int i=1;i<=n;i++){int p=lower_bound(b+1,b+cnt+1,a[i])-b;T.upd(rt[i],rt[i-1],1,cnt,p);}while(m--){int l,r,k;read(l),read(r),read(k);int id=T.query(1,cnt,rt[l-1],rt[r],k);printf("%dn",b[id]);}return 0;
}