【題目描述】

HDU - 6621 K-th Closest Distance

【題目分析】
因為看到第$k$大的要求，剛開始的時候一直都在想怎么運用第$k$大來解決問題，但是后來看其他人的博客才發現并不需要用第k大，但是主席樹維護權值線段樹還是需要的，這樣可以方便的求出某一區間內數的個數。題目要求的$|q?ai|$中第$k$大的，我們可以嘗試使用二分，只不過需要進行轉化。
我們對絕對值進行二分，左區間為0，右區間為最大的數值10⁶，對于每一個$mid$，我們查找$|q?ai|<=mid$的數字有沒有$k$個，有$k$個就減少（$r=mid?1$），否則就增加（$l=mid+1$）
現在問題的關鍵在于如何找$|q?ai|<=mid$的數字有沒有$k$個，我們可以對這個式子進行簡單的變形，去點絕對值，就能得到ai的范圍為$q?mid到q+mid$，即查找符合$q?mid到q+mid$的ai有沒有$k$個，用一個記錄權值的主席樹進行維護就能很簡單的得到。
【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int MAXN=1e5+10;
const int INF=1e6;
struct node
{int ls,rs;int sum;
}tree[MAXN*40];
int root[MAXN];
int tot;
int n,m;
int ans;void Insert(int &k,int l,int r,int x)
{tot++; tree[tot]=tree[k]; k=tot;tree[k].sum++;if(l==r){return;}int mid=(l+r)>>1;if(x<=mid) Insert(tree[k].ls,l,mid,x);else Insert(tree[k].rs,mid+1,r,x);
}int Query(int now,int pre,int l,int r,int L,int R)
{if(l>=L && r<=R){return tree[now].sum-tree[pre].sum;}int mid=(l+r)>>1;int ret=0;if(L<=mid) ret+=Query(tree[now].ls,tree[pre].ls,l,mid,L,R);if(R>mid) ret+=Query(tree[now].rs,tree[pre].rs,mid+1,r,L,R);return ret;
}int Search(int L,int R,int p,int k)
{int l=0,r=INF,mid,ret;while(l<=r){mid=(l+r)>>1;if(Query(root[R],root[L-1],1,INF,max(p-mid,1),min(p+mid,INF))>=k){ret=mid;r=mid-1;}else{l=mid+1;}}return ret;
}int main()
{int T,x,L,R,p,k;scanf("%d",&T);while(T--){tot=root[0]=tree[0].sum=tree[0].rs=tree[0].ls=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&x);root[i]=root[i-1];Insert(root[i],1,INF,x);}ans=0;for(int i=0;i<m;i++){scanf("%d%d%d%d",&L,&R,&p,&k);L=L^ans; R=R^ans; p=p^ans; k=k^ans;//if(L>R) swap(L,R);ans=Search(L,R,p,k);//這里一定要記得對ans進行賦值，忘記賦值找了好久。多組數據一定要手動檢查一下，很容易出錯printf("%d\n",ans);}}return 0;
}