CF-1072-G. Nastiness of Segments · znzryb
## 题目大意
有 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](https://codeforces.com/contest/2184/submission/358028437)
::: 源代码
```cpp
/**
* 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……）