萌新刚学主席树求组/kel
查看原帖
萌新刚学主席树求组/kel
118000
returnG楼主2020/11/11 21:28

试着用vector动态开点,然而连biuld都炸了,debug、百度无果,求大佬指教:

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m;
int a[200050],a2[200050];
struct node{
	int ls,rs;
	int sum;
};
vector<node>tr;
int biuld(int l,int r){
	tr.push_back((node){1,1,1});
	if(l==r)return 0;
	int now=tr.size()-1,mid=(l+r)>>1;
	tr[now].ls=biuld(l,mid);
	tr[now].rs=biuld(mid+1,r);
	return now;
}
int update(int u,int l,int r,int k){
	tr.push_back((node){tr[u].ls,tr[u].rs,0});
	int now=tr.size()-1;
	if(l==r){
		tr[now].sum=1;
		return now;
	}
	int mid=(l+r)>>1;
	if(k<=mid) tr[now].ls=update(tr[u].ls,l,mid,k);
	else tr[now].rs=update(tr[u].rs,mid+1,r,k);
	tr[now].sum=tr[tr[now].ls].sum+tr[tr[now].rs].sum;
}
int ask(int u,int v,int l,int r,int k){
	if(l==r)return a2[l];
	int mid=(r+l)>>1;
	if(tr[tr[u].ls].sum-tr[tr[v].ls].sum>=k)return ask(tr[u].ls,tr[v].ls,l,mid,k);
	else return ask(tr[u].rs,tr[v].rs,mid+1,r,k-(tr[tr[u].ls].sum-tr[tr[v].ls].sum));
}
int rt[200050];
int main() {
	scanf("%d%d",&n,&m);
	biuld(1,n);
	for(int i=1;i<=n;i++)a[i]=read(),a2[i]=a[i];
	sort(a2+1,a2+n+1);
	int len=unique(a2+1,a2+n+1)-a2;
	for(int i=1;i<=n;i++)a[i]=lower_bound(a2+1,a2+len,a[i])-a2;
	rt[0]=1;
	for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,n,a[i]);
	int l,r,k;
	while(m--){
		l=read();
		r=read();
		k=read();
		printf("%d\n",ask(rt[r],rt[l-1],1,n,k));
	}
	return 0;
}
2020/11/11 21:28
加载中...