# HDU 6621 (2019杭电第四场 1008) K-th Closest Distance (主席树 + 二分, 求第 k 小绝对值)

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000;
int sum[maxn*20+5];//sum为森林的不同根结点
struct E {
int num;
int l,r;
} t[maxn*20+5]; //t为tree树
int n,sz,m,a[maxn],b[maxn],cnt;
int q;
int build(int l,int r) {
int now = ++cnt;
int mid = (l+r)>>1;
if(l<r) {
t[now].l = build(l,mid);
t[now].r = build(mid+1,r);
}
return now;
}
int update(int l,int r,int last,int p) {
int now = ++cnt;
t[now].num = t[last].num+1;
t[now].l = t[last].l;
t[now].r = t[last].r;
int mid = (l + r)>>1;
if(l<r) {
if(p<=mid)t[now].l = update(l,mid,t[last].l,p);
else t[now].r = update(mid+1,r,t[last].r,p);
}
return now;
}
int query(int u,int v,int l,int r,int k){//查询区间第k大
if(l==r)return l;
// v 左孩子包含点个数减去 u 左孩子包含点的个数
int tmp = t[t[v].l].num - t[t[u].l].num;
int mid = (l+r)>>1;
if(k<=tmp)return query(t[u].l,t[v].l,l,mid,k);
else return query(t[u].r,t[v].r,mid+1,r,k - tmp);
}
int query2(int u,int v,int l,int r,int k) {//查询区间小于等于k
if(k==0)return 0;
if(l==r)return t[v].num - t[u].num;
int tmp = t[t[v].l].num - t[t[u].l].num;
int mid = (l+r)>>1;
if(k<=mid)return query2(t[u].l,t[v].l,l,mid,k);
else return tmp+query2(t[u].r,t[v].r,mid+1,r, k);
}
int l,r,pl,pr,p,k,mid,prem,pmid;
void solve(){
scanf("%d %d %d %d",&pl,&pr,&p,&k);
pl^=prem;	pr^=prem;	p^=prem;	k^=prem;
if(pl>pr)swap(pl,pr);
l = 0;	r = 1e6+5;	pmid = 0;
while(l<=r){
mid = (l+r)>>1;
int t1 = p-mid;
int t2 = p+mid;
t1 = lower_bound(b+1,b+1+sz,t1) - b - 1;
t2 = upper_bound(b+1,b+1+sz,t2) - b - 1;
if((query2(sum[pl-1],sum[pr],1,sz,t2)-query2(sum[pl-1],sum[pr],1,sz,t1))>=k){
pmid = mid;
r = mid-1;
}else l = mid+1;
}
prem = pmid;
printf("%d\n",prem);
}
int main() {
int t;
scanf("%d",&t);

while(t--) {
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
sz = unique(b+1,b+n+1) - (b+1);
cnt = 0;
sum[0] = build(1,sz);//建立空树
for(int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+sz+1,a[i]) - b;
for(int i=1; i<=n; i++) sum[i] = update(1,sz,sum[i-1],a[i]);
prem = 0;
while(m--) {
solve();
}
}
return 0;
}
/*
1
5 2
31 2 5 45 4
2 5 3 2
1 5 5 1

2
6 2
31 31 2 5 45 4
3 5 77 1
1 6 41 2
5 2
31 2 5 45 4
1 3 100 1
2 5 3 2

*/```

0 条评论

• ### HDU 1878 欧拉回路

#include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

• ### BZOJ4299: Codechef FRBSUM(主席树)

那么若\$a[i + 1] > s_i + 1\$，那么\$a[i + 1]\$不能被拼成

• ### LeetCode 周赛题解 213

因为 arr 和 pieces 中都不包含重复的数字，所以直接在pieces中暴力寻找 arr[i] 即可，然后连续的元素是否相同即可。

• ### 洛谷P4425 [HNOI/AHOI2018]转盘(线段树)

首先猜一个结论：对于每次询问，枚举一个起点然后不断等到某个点出现时才走到下一个点一定是最优的。

• ### HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是\$f[i][j]\$表示到第\$i\$位，LIS长度为\$j\$的方案。 然而发现根本不能转移，除非知道了之前的状态然后重新dp一遍。。

• ### POJ 1804 Brainman(5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

• ### 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

给你一个n行n列的格子，一开始每个格子值都是0。有M个操作，p=1为第一种操作，给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...