题目链接

• K-th Closest Distance
  • 这是一道简单的主席树题，思维难点在于是否想到二分。
  • 因为是要求区间[L, R]下标对应数列中的|p-ai|第k小值，如果我们设|p-ai|=x，我们只需保证区间[p-x, p+x]中正好有k个值，且p-x或p+x存在。
  • 二分答案x，将问题转化为判定性问题。
  • 我们发现，满足上述条件的x必是满足“区间[p-x, p+x]中有k个值”这一条件的x的最小值，二分法取下界即可。

代码：

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=(int)1e6+10;
struct Node
{
	int num,lch,rch;
	Node():num(0),lch(-1),rch(-1){}
}tree[N*20];
int tot,a[N],rt[N],qnum;
void init()
{
	tot=0;
}
void pushup(int p)
{
	tree[p].num=tree[tree[p].lch].num+tree[tree[p].rch].num;
}
int build(int l,int r)
{
	int p=tot++;
	tree[p]=Node();
	if(l==r)
	{
		tree[p].num=0;
		return p;
	}
	int mid=(l+r)>>1;
	tree[p].lch=build(l,mid);
	tree[p].rch=build(mid+1,r);
	pushup(p);
	return p;
}
int add(int p,int l,int r,int x,int y,int z)
{
	int cp=tot++;
	tree[cp]=Node();
	if(x<=l&&r<=y)
	{
		tree[cp].num=tree[p].num+r-l+1;
		return cp;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		tree[cp].lch=add(tree[p].lch,l,mid,x,y,z);
	}
	else
	{
		tree[cp].lch=tree[p].lch;
	}
	if(mid<y)
	{
		tree[cp].rch=add(tree[p].rch,mid+1,r,x,y,z);
	}
	else
	{
		tree[cp].rch=tree[p].rch;
	}
	pushup(cp);
	return cp;
}
void query(int L,int R,int x,int y,int l,int r)
{
	if(L<=l&&r<=R)
	{
		qnum+=tree[y].num-tree[x].num;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=L)
	{
		query(L,R,tree[x].lch,tree[y].lch,l,mid);
	}
	if(mid<R)
	{
		query(L,R,tree[x].rch,tree[y].rch,mid+1,r);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		init();
		int n,m;
		scanf("%d%d",&n,&m);
		rt[0]=build(1,(int)1e6);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			rt[i]=add(rt[i-1],1,(int)1e6,a[i],a[i],a[i]);
		}
		int ans=0;
		while(m--)
		{
			int L,R,p,k;
			scanf("%d%d%d%d",&L,&R,&p,&k);
			L^=ans;
			R^=ans;
			p^=ans;
			k^=ans;
			int l=0,r=(int)1e6;
			while(l<r)
			{
				int mid=(l+r)>>1;
				qnum=0;
				query(max(p-mid,1),min(p+mid,(int)1e6),rt[L-1],rt[R],1,(int)1e6);
				if(qnum>=k)
				{
					r=mid;
				}
				else
				{
					l=mid+1;
				}
			}
			printf("%d\n",ans=l);
		}
	}
	return 0;
}