CCPC 2018湘潭招待試合C題hdu 6278主席樹


HDU 6278
題意:区間内のk番目に大きい値がkに等しいときの最大のkを求める.
構想:明らかにこの最大のkを二分して求めて、更に議長の木でkの大きい値を求めてkより大きいかどうかを判断します.
​
#include
#include
#include
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn],rt[maxn*20],ls[maxn*20],rs[maxn*20],sum[maxn*20];
int cnt,ql,qr,k;
void build(int& o,int l,int r)
{
	o=++cnt;
	sum[o]=0;
	if(l==r)
	return;
	int m=(l+r)/2;
	build(ls[o],l,m);
	build(rs[o],m+1,r);
}
void update(int pre,int& o,int l,int r,int pos)
{
	o=++cnt;
	ls[o]=ls[pre];
	rs[o]=rs[pre];
	sum[o]=sum[pre]+1;
	if(l==r)
	return;
	int m=(l+r)/2;
	if(pos<=m)
	update(ls[pre],ls[o],l,m,pos);
	else
	update(rs[pre],rs[o],m+1,r,pos);
}
int query(int pre,int o,int l,int r)
{
	if(l==r)
	return b[l];
	int m=(l+r)/2;
	int cmp=sum[ls[o]]-sum[ls[pre]];
	if(cmp>=k)
	return query(ls[pre],ls[o],l,m);
	else
	{
		k-=cmp;
		return query(rs[pre],rs[o],m+1,r);
	}	
}
void work(int sz)
{
	scanf("%d%d",&ql,&qr);
	int L=1,R=qr-ql+2,m;//    +1,        bug
	while(L=m)
		{
			if(L==m)
			break;
			L=m;	
		}
		else
		R=m;
	}
	printf("%d
",m); } int main() { int n,q,i; while(~scanf("%d%d",&n,&q)) { for(i=1;i<=n;i++) { scanf("%d",&b[i]); a[i]=b[i]; } sort(b+1,b+n+1); int sz=unique(b+1,b+1+n)-(b+1); cnt=0; build(rt[0],1,sz); for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+sz,a[i])-b; for(i=1;i<=n;i++) update(rt[i-1],rt[i],1,sz,a[i]); while(q--) work(sz); } } ​