HDU6621KthClosestDistance（主席树+二分）2019暑假杭电多校第四场

题目大意&＃xff1a;

       T组&＃xff0c;n个数字&＃xff0c;m次查询&＃xff0c;每次查询 [  L , R ] 这个区间距离 q 第K小的距离。

题目思路&＃xff1a;

       考虑到K只有169范围&＃xff0c;所以可以考虑主席树&＃xff0c;主席树查询【L到R】区间中数值在【LL,RR】范围内的数字的个数。对于每组查询直接二分答案&＃xff0c;判断p-mid&＃xff0c;q&＃43;mid之间的数字够不够k个就行。

#include
#define ll long long
using namespace std;
const int MAXN&＃61;1e5&＃43;5;
int n,m;
int a[MAXN];
int L[MAXN*30],R[MAXN*30],T[MAXN],sum[MAXN*30];
int cnt&＃61;0;
int update(int pre,int l,int r,int x) ///建主席树
{int rt&＃61;&＃43;&＃43;cnt;L[rt]&＃61;L[pre];R[rt]&＃61;R[pre];sum[rt]&＃61;sum[pre]&＃43;1;int mid&＃61;(l&＃43;r)/2;if(l}
ll query(int u,int v,int l,int r,int LL,int RR) ///查询区间大于等于k的有多少个
{int ret&＃61;0;if(LL<&＃61;l&&r<&＃61;RR){return sum[v]-sum[u];}int mid&＃61;(l&＃43;r)/2;if(LL<&＃61;mid)ret&＃43;&＃61;query(L[u],L[v],l,mid,LL,RR);if(RR>mid)ret&＃43;&＃61;query(R[u],R[v],mid&＃43;1,r,LL,RR);return ret;
}int main()
{int t;scanf("%d",&t);while(t--){int Max&＃61;-1;cnt&＃61;0;scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&a[i]);Max&＃61;max(Max,a[i]);}int mm&＃61;Max;Max&＃43;&＃61;5;T[0]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){T[i]&＃61;update(T[i-1],1,Max,a[i]);}int now&＃61;0;while(m--){int l,r,p,k;scanf("%d%d%d%d",&l,&r,&p,&k);l^&＃61;now,r^&＃61;now,p^&＃61;now,k^&＃61;now;int LL&＃61;0,RR&＃61;1e6&＃43;5,ans;while(LL<&＃61;RR){int mid&＃61;(LL&＃43;RR)/2;if(query(T[l-1],T[r],1,Max,max(1,p-mid),min(mm,p&＃43;mid))>&＃61;k ){RR&＃61;mid-1;ans&＃61;mid;}else LL&＃61;mid&＃43;1;}printf("%d\n",ans);now&＃61;ans;}}
}