K-th Closest Distance

解题思路

二分答案+主席树

先建主席树，然后二分答案mid，在l和r的区间内查询[p-mid, p+mid]的范围内的数的个数，如果大于k则说明这个范围内存在第k小的数，r=mid，否则不存在，l=mid+1。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 1000005;

int rt[N], cnt;

struct T{

    int l, r;

    int lch, rch;

    int sum;

}tree[N * 30];

inline int build(int l, int r)

{

    int p = ++cnt;

    tree[p].l = l;

    tree[p].r = r;

    tree[p].lch = tree[p].rch = tree[p].sum = 0;

    if(l == r)

        return p;

    int mid = (l + r) / 2;

    tree[p].lch = build(l, mid);

    tree[p].rch = build(mid + 1, r);

    return p;

}

inline int insert(int k, int x)

{

    int p = ++cnt;

    tree[p].l = tree[k].l;

    tree[p].r = tree[k].r;

    tree[p].lch = tree[k].lch;

    tree[p].rch = tree[k].rch;

    tree[p].sum = tree[k].sum + 1;

    if(tree[k].l == tree[k].r)

        return p;

    int mid = (tree[k].l + tree[k].r) / 2;

    if(x <= mid)

        tree[p].lch = insert(tree[k].lch, x);

    else

        tree[p].rch = insert(tree[k].rch, x);

    return p;

}

int query(int k1, int k2, int l, int r)

{

    if(tree[k1].l >= l && tree[k1].r <= r)

        return tree[k2].sum - tree[k1].sum;

    int mid = (tree[k1].l + tree[k1].r) / 2;

    int m1 = 0, m2 = 0;

    if(l <= mid)

        m1 = query(tree[k1].lch, tree[k2].lch, l, r);

    if(r > mid)

        m2 = query(tree[k1].rch, tree[k2].rch, l, r);

    return m1 + m2;

}

int main()

{

    int _;

    scanf("%d", &_);

    while(_ --){

        int n, m;

        scanf("%d%d", &n, &m);

        rt[0] = build(1, 1e6);

        for(int i = 1; i <= n; i ++){

            int x = read();

            rt[i] = insert(rt[i -1], x);

        }

        int x = 0;

        for(int i = 1; i <= m; i ++){

            int l, r, p, k;

            l = read(), r = read(), p = read(), k = read();

            l ^= x, r ^= x, p ^= x, k ^= x;

            int ll = 0, rr = 1e6;

            int mid = (ll + rr) / 2;

            while(ll < rr){

                if(query(rt[l - 1], rt[r], max(1, p - mid), min(p + mid, 1000000)) >= k)

                    rr = mid;

                else

                    ll = mid + 1;

                mid = (ll + rr) / 2;

            }

            x = mid;

            printf("%d\n", x);

        }

    }

    return 0;

}

巴特西

2019杭电多校第四场hdu6621 K-th Closest Distance(二分答案+主席树)

K-th Closest Distance

解题思路

代码如下

最新文章

热门文章