题目链接:HDU6621-K-th Closest Distance
题意:
给一个长度为n的序列和m个询问,每次询问一个区间[l,r]内,第k小的|a[i]-p|的值。
题解:
二分答案+主席树(真没想到二分答案=-=
二分一个答案,然后检查区间[p-mid,p+mid]中有没有恰好k个数即可,用主席树检查。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e6 + 6;
int T;
int n, m;
int a[MAXN], b[MAXN];
int rt, tot;
int Tree[MAXN], sum[MAXN * 55], ls[MAXN * 55], rs[MAXN * 55];
void build(int l, int r, int &rt)
{
rt = ++tot;
sum[rt] = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(l, mid, ls[rt]);
build(mid + 1, r, rs[rt]);
}
void update(int las, int val, int l, int r, int &rt)
{
rt = ++tot;
ls[rt] = ls[las];
rs[rt] = rs[las];
sum[rt] = sum[las] + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
if (val <= mid)
update(ls[las], val, l, mid, ls[rt]);
else
update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int lt, int rt)
{
if (L <= l && r <= R)
{
return sum[rt] - sum[lt];
}
int mid = (l + r) / 2;
int res = 0;
if (L <= mid)
res += query(L, R, l, mid, ls[lt], ls[rt]);
if (R > mid)
res += query(L, R, mid + 1, r, rs[lt], rs[rt]);
return res;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
int N = MAXM;
tot = 0;
build(1, n, Tree[0]);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
update(Tree[i - 1], a[i], 1, N, Tree[i]);
}
int prex = 0;
while (m--)
{
int l, r, p, k;
scanf("%d%d%d%d", &l, &r, &p, &k);
l ^= prex, r ^= prex, p ^= prex, k ^= prex;
int ll = 0, rr = N;
while (ll <rr)
{
int mid = (ll + rr) / 2;
if (query(max(1, p - mid), min(N, p + mid), 1, N, Tree[l - 1], Tree[r]) >= k)
{
prex = mid;
rr = mid;
}
else
ll = mid + 1;
}
printf("%d\n", prex);
}
}
return 0;
}