我擦终于A了这题了！

主席树坑点多……

最好不要写指针主席树，不然容易TLE……（自带常数？）

并且注意，一定要把数组开大，开大，再开大，重要的事情说三遍

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100001,maxnode=maxn*20;
int sumv[maxnode];
int lc[maxnode];
int rc[maxnode];
int root[maxn];
int A[maxn];
int A2[maxn];
int size,tot=0;
int build_tree(int L,int R){
	++tot;
	if(L==R)
		return tot;
	int ans=tot,M=L+(R-L)/2;
	lc[ans]=build_tree(L,M);
	rc[ans]=build_tree(M+1,R);
	return ans;
}
int p;
int update(int o,int L,int R){
	int roo=++tot;
	sumv[roo]=sumv[o];
	lc[roo]=lc[o];
	rc[roo]=rc[o];
	if(R>L){
		int M=L+(R-L)/2;
		if(p<=M)
			lc[roo]=update(lc[tot],L,M);
		else
			rc[roo]=update(rc[tot],M+1,R);
	}
	sumv[roo]++;
	return roo;
}
int query(int lo,int ro,int L,int R,int k){
	if(L==R)
		return L;
	int M=L+(R-L)/2,lc_siz=sumv[lc[ro]]-sumv[lc[lo]];
	if(k<=lc_siz)
		return query(lc[lo],lc[ro],L,M,k);
	else
		return query(rc[lo],rc[ro],M+1,R,k-lc_siz);
}
void init_tree(int n){
	register int i;
	sort(A2,A2+n);
	size=unique(A2,A2+n)-A2;
	root[0]=build_tree(1,size);
	for(i=1;i<=n;i++){
		p=lower_bound(A2,A2+size,A[i-1])-A2+1;
		root[i]=update(root[i-1],1,size);
	}
}
int main(){
	int n,m,u,v,k;
	register int i;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
		A2[i]=A[i];
	}
	init_tree(n);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&u,&v,&k);
		printf("%d\n",A2[query(root[u-1],root[v],1,size,k)-1]);
	}
	return 0;
}

• 相关文章
• 全局相关文章