icontofig | 发布于 2020-02-10 23:17:59 | 阅读量 227 | 二分 可持久化线段树 可持久化数据结构
发布于 2020-02-10 23:17:59 | 二分 可持久化线段树 可持久化数据结构

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

题目大意

给出一个序列,有m组询问。

每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。

题解

看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。

然后问题就在于这个check如何去操作。

如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢?

这个没法做到,我们只能去确定,是否存在连续w的区间的数全部大于等于mid。

我们假设当前二分到的值为mid,大于等于mid的数都设为1,小于mid的数都设为0,那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。

但是我们注意到一些问题,序列中的数比较大,直接二分的话常数会大些,而且也没有办法对每次二分的mid建一棵线段树去check,时间上会炸掉。

这种情况下我们可以考虑将序列中的值从大到小排序,保留其原先所在的位置下标,对排完序之后的值,我们可以直接用序列进行二分。

而在排完序的情况下,可以注意到,以当前位置的值为check的值时,其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。

这个修改只有一次,因此可以建立可持久化线段树进行check。

当前二分的位置为mid时,对root[mid]对应的线段树进行check,检索是否可行就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
    int h;
    int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
    int l,r;
    int lc,rc;
    int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
    tr[now].len = tr[tr[now].lc].len + tr[tr[now].rc].len;
    tr[now].suml = tr[tr[now].lc].suml;
    if(tr[tr[now].lc].suml == tr[tr[now].lc].len)
        tr[now].suml += tr[tr[now].rc].suml;
    tr[now].sumr = tr[tr[now].rc].sumr;
    if(tr[tr[now].rc].sumr == tr[tr[now].rc].len)
        tr[now].sumr += tr[tr[now].lc].sumr;
    tr[now].sum = max(tr[tr[now].lc].sum,tr[tr[now].rc].sum);
    tr[now].sum = max(tr[now].sum,tr[tr[now].lc].sumr + tr[tr[now].rc].suml);
    return;
}
int build(int l,int r){
    int now = ++cnt;
    tr[now].l = l;
    tr[now].r = r;
    if(l == r){
        tr[now].suml = tr[now].sum = tr[now].sumr = 0;
        tr[now].len = 1;
        return now;
    }
    int mid = (l + r) >> 1;
    tr[now].lc = build(l,mid);
    tr[now].rc = build(mid+1,r);
    push_up(now);
    return now;
}
int update(int last,int pos){
    int now = ++cnt;
    tr[now] = tr[last];
    if(tr[now].l == pos && tr[now].r == pos){
        tr[now].suml = tr[now].sumr = tr[now].sum = 1;
        tr[now].len = 1;
        return now;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)
        tr[now].lc = update(tr[last].lc,pos);
    else tr[now].rc = update(tr[last].rc,pos);
    push_up(now);
    return now;
}
int lt;
int query(int now,int l,int r){
    int res = 0;
    if(tr[now].l >= l && tr[now].r <= r){
        res = max(res,tr[now].sum);
        lt += tr[now].suml;
        res = max(res,lt);
        if(tr[now].suml != tr[now].len){
            lt = tr[now].sumr;
            res = max(res,lt);
        }
        return res;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(r <= mid)res = query(tr[now].lc,l,r);
    else if(l > mid)res = query(tr[now].rc,l,r);
    else{
        res = max(res,query(tr[now].lc,l,r));
        res = max(res,query(tr[now].rc,l,r));
    }
    return res;
}
bool cmp(height a,height b){
    return (a.h > b.h || (a.h == b.h && a.id > b.id));
}
int k,l,r;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i].h;
        a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);
    rt[0] = build(1,n);
    for(int i = 1;i <= n;++i){
        rt[i] = update(rt[i-1],a[i].id);
    }
    cin >> q;
    while(q--){
        cin >> u >> v >> k;
        l = 1,r = n;
        int ans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            lt = 0;
            if(query(rt[mid],u,v) >= k){
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        cout << a[ans].h << "\n";
    }
    return 0;
}



内容更新于: 2020-02-10 23:18:04
链接地址: http://blog.leanote.com/post/icontofig/CodeForces-484E-Sign-on-Fence-e

上一篇: CodeForces - 1055F Tree and XOR 01-Trie

下一篇: 51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心

227 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航