题解：AT_abc428_f [ABC428F] Pyramid Alignment

__FL__ · 2025-10-19 11:31:16 · 题解

AT_abc428_f [ABC428F] Pyramid Alignment

Problem

有 N 个滑块叠成一摞，从上往下第 i 个滑块的长为 w_i，且上面滑块的长度总是严格小于下面滑块的长度。初始时，每个滑块的左端点都为 0。

现在有 Q 组询问，对询问 1 和 2，需将所有位于 v 上的滑块的左端点/右端点设为 v 的左端点/右端点；对询问 3，询问覆盖了点 x+0.5 的滑块数量。

Solution

考虑一个性质：若点 x 被滑块 v 覆盖到了，则滑块 v 及其以下的滑块一定都可以覆盖 x，显然这是具有单调性的，那么我们可以二分最上面的可以覆盖 x 的滑块 i，最后 n-i+1 即为答案。我们考虑如何维护每个滑块的位置信息。

对于一个滑块，无论我们明确了它的左端点还是右端点，都能的到它的位置信息。那么对于一次修改操作，我们先求出滑块 v 的左端点/右端点，然后对它上面的滑块做区间覆盖（另一个端点赋为 -1 表示尚不明确）。这样无论何时我们总是能得知滑块 i 其中一个端点的位置。

Time complexity

二分+线段树，时间复杂度 O(n\log ^2n)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,q,w[N];
struct node
{
    int l,r;
}f[N<<2],g[N<<2];
void build(int root,int l,int r)
{
    if (l >= r)
    {
        f[root] = {0,-1};
        return;
    }
    int mid = (l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
}
inline void pushdown(int root)
{
    f[root*2] = f[root*2+1] = g[root*2] = g[root*2+1] = g[root];
    g[root] = {0,0};
}
void update(bool isl,int root,int l,int r,int ql,int qr,int x) //isl表示覆盖的是左端点还是右端点
{
    if (ql <= l && qr >= r)
    {
        if (isl) f[root] = g[root] = {x,-1};
        else f[root] = g[root] = {-1,x};
        return;
    }
    if (g[root].l != 0 || g[root].r != 0) pushdown(root);
    int mid = (l+r)/2;
    if (qr <= mid) update(isl,root*2,l,mid,ql,qr,x);
    else if (ql > mid) update(isl,root*2+1,mid+1,r,ql,qr,x);
    else update(isl,root*2,l,mid,ql,mid,x),update(isl,root*2+1,mid+1,r,mid+1,qr,x);
}
node query(int root,int l,int r,int x)
{
    if (l >= r) return f[root];
    if (g[root].l != 0 || g[root].r != 0) pushdown(root);
    int mid = (l+r)/2;
    if (x <= mid) return query(root*2,l,mid,x);
    return query(root*2+1,mid+1,r,x);
}
inline int get_x_l(int x)
{
    node k = query(1,1,n,x);
    if (k.l == -1) return k.r-w[x];
    return k.l;
}
inline int get_x_r(int x)
{
    node k = query(1,1,n,x);
    if (k.r == -1) return k.l+w[x];
    return k.r;
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    build(1,1,n);
    cin >> q;
    while (q--)
    {
        int op,x;
        cin >> op >> x;
        if (op == 1)
        {
            update(1,1,1,n,1,x,get_x_l(x));
        }
        else if (op == 2)
        {
            update(0,1,1,n,1,x,get_x_r(x));
        }
        else
        {
            int l = 1,r = n+1;
            while (l < r)
            {
                int mid = (l+r)/2;
                if (x+0.5 >= get_x_l(mid) && x+0.5 <= get_x_r(mid)) r = mid;
                else l = mid+1;
            }
            cout << n-l+1 << '\n';
        }
    }
    return 0;
}