P4198 楼房重建题解

线段树二分

思路

考虑在线段树内维护二信息：

区间斜率最大值 \(mx\)
区间最大斜率上升序列长度 \(len\)

答案即为根节点的 \(len\)。

考虑转移信息二：

蓝色部分代表左区间的上升序列，红色是右区间的，绿色折线就是当前区间的上升序列。

?稍微思考之后发现，左区间的上升序列一定完整存在于当前区间的上升序列，那么右区间对当前区间的贡献就只有右区间的上升序列中斜率大于左区间斜率最大值 \(left.mx\)（蓝色部分中最长线段）的部分。

可以发现，第一个大于 \(left.max\) 的右区间部分把右区间分为了两部分，这满足二分性和单调性，因此我们可以线段树二分：

int up(int k, double v) // 求 k 节点区间内大于v的上升斜率序列的长度
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    
    if(l == r) return tr[k].mx > v; 
    // 如果叶子节点只需要考虑当前这个点即可
    
    if(ls.mx <= v) return up(k << 1 | 1, v); 
    // 如果左区间最大值小于等于v意味着左区间毫无贡献，只看有区间
    
    else return up(k << 1, v) + tr[k].len - tr[k << 1].len;
    // 如果左区间有贡献先看左区间，然后加上右区间中大于 v 的上升斜率序列的长度
}

完整代码

// Problem: P4198 楼房重建
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-05-02 16:04:09

#include <iostream>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define INF (int)1e9
using namespace std;

const int N = 1e5 + 10;

struct qwq
{
    int l, r;
    double mx;
    int len;
} tr[N << 2];

#define ls tr[k << 1]
#define rs tr[k << 1 | 1]

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if(l != r) 
        build(u << 1, l, l + r >> 1), build(u << 1 | 1, (l + r >> 1) + 1, r);
}

int up(int k, double v) // k 节点区间内大于v的上升斜率序列的长度
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    
    if(l == r) return tr[k].mx > v; 
    // 如果子节点只需要考虑当前这个点即可
    
    if(ls.mx <= v) return up(k << 1 | 1, v); 
    // 如果左区间最大值小于等于v意味着左区间毫无贡献，只看有区间
    
    else return up(k << 1, v) + tr[k].len - tr[k << 1].len;
    // 如果左区间有贡献先看左区间，然后加上右区间中大于 v 的上升斜率序列的长度
}

void update(int k, int x, double v)
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    if(x == l && x == r)
    {
        tr[k].mx = v;
        tr[k].len = 1; // 题目保证 y >= 1
        return ;
    }
    if(x <= mid) update(k << 1, x, v);
    else update(k << 1 | 1, x, v);
    tr[k].mx = max(ls.mx, rs.mx);
    tr[k].len = ls.len + up(k << 1 | 1, ls.mx); 
    // 左区间的上升序列一定选择，这是显而易见的
}

signed main()
{
    speedup;
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        update(1, x, 1.0 * y / x);
        cout << tr[1].len << '\n';
    }

    return 0;
}