CF-1072-G. Nastiness of Segments

题目大意

有 n 个块，编号从 1 到 n，每个块上有一个初始整数 a_i。

对于一个连续段 [l, r]，如果整数 d (0 ≤ d ≤ r - l) 满足 $min(a_l, a_{l+1}, ..., a_{l+d}) = d$，则称 d 为 nasty 数字。

一个段的 nastiness 定义为该段中 nasty 数字的数量。

需要处理 q 个操作：

• **操作 1：**将第 i 个块上的数字修改为 x

• **操作 2：**查询段 [l, r] 的 nastiness

对于每个操作 2，输出对应段的 nastiness 值。

思路讲解

我们发现一件事情，令 $mn\gets min(a_l, a_{l+1}, …, a_{l+d}) $，$d\uparrow$，$mn\downarrow$，他们两个的这个单调关系是相反的，我们却要求的是 $mn=d$ 的这个情况的数量，由于 $d$ 是严格递增的，$mn$ 是非严格递减的，这两者显然最多只有一个交点。

那么现在这个问题就来到了，我们实际上就是求一个区间中是否有这个 $d$ 值嘛，显然，这个可以使用二分解决，只要我们有一个数据结构可以支持这个 RMQ 和这个单点修改即可，可以使用我们的树状数组。

AC代码

AC
https://codeforces.com/contest/2184/submission/358028437

源代码

/**
 * Problem: G. Nastiness of Segments
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/G
 * Created: 2026-01-16 09:39:42
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
// by Gospel_rock znzryb
// 参考了（抄了）OIwiki
// https://www.luogu.com.cn/record/228807838 ST表模版题（max）
// https://www.luogu.com.cn/record/228809172 打乱了插入顺序，和上面是同一道
struct RMQ{
    const ll dummy=INF;
    ll n;vector<ll> tr;vector<ll> origin;
    inline ll lowbit(const ll &x){
        return x&-x;
    }
private:
    ll op(const ll &a,const ll &b){
        return min(a,b);
    }
public:
    RMQ(ll n){
        this->n=n+2;
       tr.resize(n+5,INF),origin.resize(n+5);
    }
    ll query(ll l,ll r){
        ll res=dummy;
        while (r>=l) {
            res=op(origin[r],res);
            r--;
            for(;r-lowbit(r)>=l;r-=lowbit(r)){
                res=op(res, tr[r]);
            }
        }
        return res;
    }
    void upd(ll p,ll x){    // 其实不是增加
        origin[p]=x;
        for(int i=p;i<=n;i+=lowbit(i)){
            tr[i]=origin[i];
            for(int j=1;j<lowbit(i);j<<=1){
                tr[i]=op(tr[i],tr[i-j]);
            }
        }
    }
};
void Solve() {
    ll N,Q;
    cin >> N >> Q;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    RMQ tr(N);
    for (int i=1;i<=N;++i) {
        tr.upd(i,A[i]);
    }
    for (int _=1;_<=Q;++_) {
        ll op;
        cin>>op;
        if (op==1) {
            ll pos,x;
            cin>>pos>>x;
            tr.upd(pos,x);
        }else {
            ll l,r;
            cin>>l>>r;
            ll bsl=0,bsr=r-l;
            auto check=[&](ll x) {
                ll mn=tr.query(l,l+x);
                if (mn>x) {
                    return 0;
                }
                if (mn==x) return 1;
                return 2;
            };
            while (bsl<bsr) {
                ll mid=(bsl+bsr)>>1;
                if (check(mid)) {
                    bsr=mid;
                }else {
                    bsl=mid+1;
                }
            }
            if (check(bsl)==1) {
                cout<<1<<"\n";
            }else {
                cout<<0<<"\n";
            }
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）