2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树(主席树)
二分 可持久化线段树   发布于 2019-08-01   246人围观  0条评论
二分 可持久化线段树   发表于 2019-08-01   246人围观  0条评论

题目大意

给你一个长为n的序列,有q次询问,每次询问回答区间[l,r]中离p距离第k小的数距离p有多远(距离指在数轴上的距离,也就是差的绝对值)

题目强制在线。

题解

我们首先可以把问题转化为这样:

假设询问的答案为ans,那么就代表着区间[l,r]内的数中,在范围[p-ans,p+ans]中有k个。

所以我们就可以枚举答案,然后去查询区间[l,r]内的符合要求的数的个数。

但是枚举效率过于低下,我们又发现这个答案是具有二分性的,所以我们将枚举答案改为二分答案并且检查。

然后再来看我们怎么统计区间[l,r]内在范围[p-ans,p+ans]的数的个数。

一般来讲,我们判断在范围[p,k]内的数的个数,可以使用权值线段树,维护区间内所有数个数总和,然后查询。

但是此题还要求我们在限定的区间[l,r]内去寻找,所以我们就要使用可持久化权值线段树,也就是主席树维护。

主席树的最经典功能就是可以在静态区间内(无修改操作)查询排名第k的数,而这种功能的实现,实际上也是靠权值线段树统计区间内有多少小于x的数来实现的。

所以我们可以直接使用主席树的权值线段树所有的功能,直接寻找区间[l,r]内在范围[p-ans,p+ans]内的数。

(主席树的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;
}


上一篇: Codeforces 965E Short Code Trie树+贪心(启发式合并)

下一篇: 主席树模板

立即登录,发表评论
没有帐号?立即注册
0 条评论