CF56E 题解

题面

设骨牌 \(i\) 倒下之后会连带压倒 \([i+1,r_i]\) 的骨牌，那么有

\(z_i=\max_{j=i+1}^{r_i}z_j+(j-i)\)

考虑线段树优化 dp，但是 \((j-i)\) 不好维护，所以套路地修改式子，得到：

\(z_i+i=\max_{j=i+1}^{r_i}(z_j+j)\)

所以线段树维护 \(z_i+i\) 的区间最大值即可，\(r_i\) 可以二分求出。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

struct sgt
{
    int a[N << 2];
    void pu(int x)
    {
        a[x] = max(a[x << 1], a[x << 1 | 1]);
    }
    void upd(int q, int l, int r, int x, int v)
    {
        if(l == r) return a[x] = v, void();
        int mid = l + r >> 1;
        if(mid >= q) upd(q, l, mid, x << 1, v);
        else upd(q, mid + 1, r, x << 1 | 1, v);
        pu(x);
    }
    int qry(int ql, int qr, int l, int r, int x)
    {
        if(ql <= l && r <= qr) return a[x];
        int mid = l + r >> 1, ans = 0;
        if(mid >= ql) ans = max(ans, qry(ql, qr, l, mid, x << 1));
        if(mid < qr) ans = max(ans, qry(ql, qr, mid + 1, r, x << 1 | 1));
        return ans;
    }
    void build(int l, int r, int x)
    {
        if(l == r) return a[x] = l, void();
        int mid = l + r >> 1;
        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pu(x);
    }
} t;

struct node{int pos, h, id;} a[N];
int pos[N], ans[N], id[N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n; cin >> n;
    t.build(1, n, 1);
    for(int i = 1; i <= n; i ++) cin >> a[i].pos >> a[i].h, a[i].id = i;
    sort(a + 1, a + n + 1, [](auto &x, auto &y) {return x.pos < y.pos;});
    for(int i = 1; i <= n; i ++) id[a[i].id] = i;
    for(int i = 1; i <= n; i ++) pos[i] = a[i].pos;
    t.upd(n, 1, n, 1, n + 1);
    ans[n] = 1;
    for(int i = n - 1; i >= 1; i --)
    {
        int r = lower_bound(pos + 1, pos + n + 1, a[i].pos + a[i].h) - pos - 1;
        if(r == i)
        {
            t.upd(i, 1, n, 1, i + 1);
            ans[i] = 1;
            continue;
        }
        int k = t.qry(i + 1, r, 1, n, 1);
        t.upd(i, 1, n, 1, k);
        ans[i] = k - i;
    }
    for(int i = 1; i <= n; i ++) cout << ans[id[i]] << " ";

    return 0;
}