2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树（主席树）

## 题解

（主席树的root[r]为时刻r的权值线段树的根，也就是表示区间1——r存储的权值线段树的根，当理解这一点以后主席树就没有那么难了）。

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
struct tree{
int l,r;
tree *lc,*rc;
int sum;
}pool[maxn<<4],*root[maxn],*null;
int cnt = 0;
int a[maxn];
int b[maxn];
int n,q;
int tot = 0;
int l,r,k,p,x;
int T;
void init(){
x = 0;
null = pool;
null->sum = 0;
null->lc = null->rc = null;
null->l = null->r = 0;
return;
}
tree *new_node(){
tree *node = pool + ++cnt;
node->lc = node->rc = null;
node->sum = 0;
node->l = node->r = 0;
return node;
}
tree *build(int l,int r){
tree *node = new_node();
node->l = l;
node->r = r;
if(l == r)return node;
int mid = (l + r) >> 1;
node->lc = build(l,mid);
node->rc = build(mid+1,r);
return node;
}
tree *update(tree *pre,int x){
if(pre == null)return null;
tree *now = new_node();
now->lc = pre->lc;
now->rc = pre->rc;
now->l = pre->l;
now->r = pre->r;
now->sum = pre->sum + 1;
if(now->lc == now->rc)
return now;
int mid = (now->l + now->r) >> 1;
if(x <= mid)
now->lc = update(pre->lc,x);
else now->rc = update(pre->rc,x);
return now;
}
int mx = 0;
int query(tree *ll,tree *rr,int lt,int rt){
if(ll->l >= lt && rr->r <= rt)
return rr->sum - ll->sum;
if(rr == null)return 0;
int mid = (ll->l + rr->r) >> 1;
int ans = 0;
if(mid >= lt)ans += query(ll->lc,rr->lc,lt,rt);
if(mid < rt)ans += query(ll->rc,rr->rc,lt,rt);
return ans;
}//
void work(int l,int r,int p,int k){
int ll = 0,rr = mx,mid,ans = -1;
int lx,rx;
while(ll <= rr){
mid = (ll + rr) >> 1;
lx = max(0,p - mid);
rx = min(mx,p + mid);
if(query(root[l-1],root[r],lx,rx) >= k){
ans = mid;
rr = mid - 1;
}
else ll = mid + 1;
}
printf("%d\n",ans);
x = ans;
return;
}
int main(){
freopen("data.in","r",stdin);
T = get_num();
while(T--){
init();
n = get_num();
cnt = 0;
q = get_num();
for(int i = 1;i <= n;++i){
a[i] = get_num();
b[i] = a[i];
mx = max(mx,a[i]);
}
root[0] = build(1,mx);
for(int i = 1;i <= n;++i){
root[i] = update(root[i-1],a[i]);
}
while(q--){
l = get_num();
r = get_num();
p = get_num();
k = get_num();
l ^= x;
r ^= x;
p ^= x;
k ^= x;
work(l,r,p,k);
}
}
return 0;
}```

0 条评论