Znzryb's Blog

CF-1081-赛后总结（不同的值就用不同的变量，不要用同一个变量，可能会导致漏写错写，请尽量少的复用原有的变量）

Posted on 2026-02-21 Edited on 2026-02-22

基本情况

打的还是挺不错的。一共做出来四道题，做出来四道题。这个 D 题是最后 A 的，D 题是最后 A 的。哎，D 题这个叫什么，稍微有点唐了，这漏了这两行有点唐了。还有这个 C 啊，读错题目了。这个 C 读错题目了，绷不住了，我自己给自己上难度啊，以为这个弹夹可以不打完就就换，这个弹夹可以不打完就换，自己给自己上难度。以后遇到这个题目啊，就是如果我们发现这道题目，就是我们还是要确定一下，就是一些限制条件，我们还是要想办法确定一下。

然后这个 d 的这个情况也是比较唐的，就这个 d 漏的这两行比较唐吧。是这样子，我感觉呢，以后这种如果说有多个，然后需要取 max 的话，最好啊最好就是多整几行，多整几个变量，整个 add1 add2，这样子就你你不会忘记去给它进行这么一个赋值。然后你 add 1，你写出来，你不用，编译器还会报警，IDE 还会报警，对吧？你 add 1没用，你就知道你要把它取个 max 对吧？

https://codeforces.com/contest/2192

if (a.id!=b.id) {
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
}else {
    a=*prev(prev(mx_diff_st.end()));
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
    a=*mx_diff_st.rbegin();
    b=*prev(prev(mx_a_st.end()));
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
}

心得感悟

下面是和队友对 D 题的这个探讨。

ZnZrYb: 02-22 00:36:59
首先是树上 dp

ZnZrYb: 02-22 00:37:38
auto dfs2=[&](auto && self,ll u,ll p,ll dep) -> void {
dep_ls[u]=dep;
set<Dep_sub> mx_diff_st;
set<A_sub> mx_a_st;
ll id=0;
ll add_mx=0;
for (auto to:g[u]) {
if (to==p) continue;
self(self,to,u,dep+1);
dp[u]+=dp[to];
dp[u]+=sum_a[to];
sum_a[u]+=sum_a[to];
add_mx=max(add_mx,ans_ls[to]-dp[to]);
mx_dep[u]=max(mx_dep[to],mx_dep[u]);
++id;
mx_diff_st.insert({id,mx_dep[to]-dep});
mx_a_st.insert({id,sum_a[to]});
}
if (id>=2) {
Dep_sub a=mx_diff_st.rbegin();
A_sub b=mx_a_st.rbegin();
ll add=0;
if (a.id!=b.id) {
add=a.dep*b.suma;
add_mx=max(add,add_mx);
}else {
a=prev(prev(mx_diff_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
a=*mx_diff_st.rbegin();
b=prev(prev(mx_a_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
}
}
ans_ls[u]=dp[u]+add_mx;
sum_a[u]+=A[u];
mx_dep[u]=max(dep,mx_dep[u]);
};

ZnZrYb: 02-22 00:37:54
答案在这个 ans

鵗曦: 02-22 00:39:12
我是先枚举移动各个节点，显然移动该节点最好办法就是移动到子树外的最深节点，移完之后贡献变化是高度差乘以子树的系数和

ZnZrYb: 02-22 00:39:19
具体来说就是这个增量可以从，就是子节点里面来，就是可以从子节点里面来。然后这个增量也可以就是我们自己来操作。自己来操作的话，是使用的 Max D I F F S T 和 Max A S T。其实就是把最大的 sum A 嫁接到最大的深度指数上。但如果说最大的深度指数和最大的 sum A 是同一个的话，需要稍微进行一下其他处理。

鵗曦: 02-22 00:39:29
然后每个节点的答案就是子树的最大值。

鵗曦: 02-22 00:40:10
我是这么想的，但是写不对。

鵗曦: 02-22 00:40:48
你觉得对不对

鵗曦: 02-22 00:40:51
[图片]

鵗曦: 02-22 00:41:14
diffst和ast是啥玩意

ZnZrYb: 02-22 00:42:13
diff_st 存的是子树深度差值。 AST 就是存的是子树权值和

ZnZrYb: 02-22 00:43:01
我觉得这个思路挺对的

鵗曦: 02-22 00:43:53
按我这么写，需要用的信息可以O（n）维护出来。唯一的难点就是要查子树外的最深节点

鵗曦: 02-22 00:44:02
然后咱想的是上个树剖

ZnZrYb: 02-22 00:44:15
啊

鵗曦: 02-22 00:44:24
因为一个子树在dfn上是连续的。

鵗曦: 02-22 00:44:37
所以可以查前面一整段和后面一整段，取其中的深度最大值。

鵗曦: 02-22 00:44:44
但是写的不对

鵗曦: 02-22 00:44:51
[图片]

ZnZrYb: 02-22 00:44:55
懂了

ZnZrYb: 02-22 00:45:50
那就上个 st 表都能解决

ZnZrYb: 02-22 00:46:03
感觉挺对的

鵗曦: 02-22 00:46:13
过不去样例

鵗曦: 02-22 00:46:16
写炸了

ZnZrYb: 02-22 00:46:21
[笑哭]

鵗曦: 02-22 00:46:57
dfn序列用st表预处理是吧

鵗曦: 02-22 00:47:14
咱的树剖板子默认写了线段树

ZnZrYb: 02-22 00:47:22
哦，我知道你可能是哪里的问题了

鵗曦: 02-22 00:47:41
哪里

ZnZrYb: 02-22 00:48:34
不过我不确定，就是你限定了树的范围了吧，就是他求的是 i 的子树

ZnZrYb: 02-22 00:48:38
的答案

鵗曦: 02-22 00:49:16
不是输出每个节点对应的答案吗

鵗曦: 02-22 00:49:26
每个节点的操作是可以任意选择它指数里面的一个节点进行嫁接

鵗曦: 02-22 00:49:34
子树

鵗曦: 02-22 00:49:57
所以每个节点的答案就是处理出来的子树里的最大值。

ZnZrYb: 02-22 00:51:36
感觉好像你没有理解错啊，你也是查询的子树里深度最大值是吧

鵗曦: 02-22 00:52:09
我已经枚举计算过了，假如要移动某某个节点，能产生的最大权重

鵗曦: 02-22 00:52:35
所以输出答案的时候，对于一个节点的答案，只需要找这个节点所在的子数里面计算出的各个最大权重中的最大

鵗曦: 02-22 00:52:47
当然也是O（n）就能弄出来的。

ZnZrYb: 02-22 00:53:41
子树里面的这个点，是连到子树里面，还是连到子树外面

ZnZrYb: 02-22 00:54:22
如果计算 i 的答案，子树 i 里面的点必须只能连接到子树 i 的里面的其他点

鵗曦: 02-22 00:54:34
6

鵗曦: 02-22 00:54:37
这里理解错了

鵗曦: 02-22 00:55:15
那我这样反着做错完了。

2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——I. Cutting Trees（这种题目呢，显然是需要你去观察得到一个结论。但是怎么样去观察呢？往往这些题目具有自相似的这个特性，因此我们可以从一层开始，先只考虑一层，然后再考虑下面一层，分层的去解决这个问题）

Posted on 2026-02-19 Edited on 2026-02-20

题目大意

第 1 棵树：仅包含节点 $1$ 。
第 2 棵树：加入节点 $2$ 并与节点 $1$ 相连，根节点为 $2$ 。
第 $n$ 棵树的构建（由第 $n-1$ 棵树生成）：
1. 从第 $n-1$ 棵树的根节点出发，向下寻找一条通往叶子节点的路径。在每一步选择子节点时，总是选择编号最大的那个子节点。
2. 删除该路径上原有的所有边。
3. 加入编号为 $n$ 的新节点，将 $n$ 与刚才路径上的每一个节点分别用一条边相连。
4. 节点 $n$ 成为第 $n$ 棵树的新根。

问题描述

给定两个整数 $n$ 和 $v$ （ $1 \le v \le n \le 10^{18}$ ），请计算在第 $n$ 棵树中，从根节点（节点 $n$ ）到节点 $v$ 的最短路径上，所有经过节点的编号之和（包含起点 $n$ 和终点 $v$ ）。

输入格式

一行包含两个整数 $n$ 和 $v$ 。

输出格式

输出一个整数 $S$ ，表示路径节点编号之和。

样例数据

Input
2 1
Output
3

Input
3 2
Output
5

Input
6 1
Output
12

Input
9 6
Output
23

样例解释

以 6 1 为例（输出 12）：

T2：根 $2$ ，边 $(2,1)$ 。
T3：T2 路径为 $2 \to 1$ 。删除 $(2,1)$ 。加入 $3$ ，连接 $(3,2), (3,1)$ 。根 $3$ 。
T4：T3 根 $3$ ，子节点 $\{2, 1\}$ ，最大子节点 $2$ （叶子）。路径 $3 \to 2$ 。删除 $(3,2)$ 。加入 $4$ ，连接 $(4,3), (4,2)$ 。保留 $(3,1)$ 。根 $4$ 。
T5：T4 根 $4$ ，子节点 $\{3, 2\}$ ，最大子节点 $3$ （ $3$ 连 $1$ ）。路径 $4 \to 3 \to 1$ 。删除 $(4,3), (3,1)$ 。加入 $5$ ，连接 $(5,4), (5,3), (5,1)$ 。保留 $(4,2)$ 。根 $5$ 。
T6：T5 根 $5$ ，子节点 $\{4, 3, 1\}$ ，最大子节点 $4$ （ $4$ 连 $2$ ）。路径 $5 \to 4 \to 2$ 。删除 $(5,4), (4,2)$ 。加入 $6$ ，连接 $(6,5), (6,4), (6,2)$ 。保留 $(5,3), (5,1)$ 。根 $6$ 。
查询：在 T6 中从 $6$ 到 $1$ 。由于 $6$ 直接连接 $5$ ，且 $5$ 此时保留了与 $1$ 的连接（ $(5,1)$ 在生成 T6 时未被选中删除），路径为 $6 \to 5 \to 1$ 。
结果： $6 + 5 + 1 = 12$ 。

思路讲解

AI 提示 1

这道题的关键在于发现树的递归自相似结构。让我带你一步步找到规律。
观察一：根的孩子有什么规律？
把每棵树根节点的孩子列出来：

$T_2$ ：孩子 = $\{1\}$
$T_3$ ：孩子 = $\{2, 1\}$
$T_4$ ：孩子 = $\{3, 2\}$
$T_5$ ：孩子 = $\{4, 3, 1\}$
$T_6$ ：孩子 = $\{5, 4, 2\}$
$T_9$ ：孩子 = $\{8, 7, 5, 1\}$
规律：根 $n$ 的孩子恰好是 $n-1, n-2, n-4, n-8, \ldots$ （即 $n - 2^j$ ，直到减出的值 $\le 0$ ）。这可以通过分析最大子节点路径来证明——该路径恰好经过 $n-1, n-2, n-4, \ldots$ 。
观察二：子树的自相似结构
第 $j$ 个孩子 $c_j = n - 2^j$ 的子树里，所有节点等间距排列，间距为 $2^{j+1}$ 。例如在 $T_9$ 中：
孩子 $8$ （ $j=0$ ）的子树： $\{8, 6, 4, 2\}$ ，间距 $2$
孩子 $7$ （ $j=1$ ）的子树： $\{7, 3\}$ ，间距 $4$
孩子 $5$ （ $j=2$ ）的子树： $\{5\}$ ，间距 $8$
而且每个子树的内部结构和某个更小的 $T_m$ 完全同构！
观察三（核心）：如何判断 $v$ 在哪个子树里？
计算 $d = n - v$ ，然后求 $d$ 的二进制末尾零的个数 $j = \nu_2(d)$ ， $v$ 就在第 $j$ 个孩子 $n - 2^j$ 的子树中。
验证（ $T_9$ 中）：
$v=6$ ： $d=3=11_2$ ， $j=0$ → 在孩子 $8$ 的子树 ✓
$v=3$ ： $d=6=110_2$ ， $j=1$ → 在孩子 $7$ 的子树 ✓
$v=1$ ： $d=8=1000_2$ ， $j=3$ → 在孩子 $1$ 的子树 ✓
观察四：递归下降求路径
进入子树后，"根"变为 $c_j$ ，"步长"变为 $b \cdot 2^{j+1}$ ，然后重复同样的过程。每一步步长至少翻倍，所以总共只需 $O(\log n)$ 步。
整个算法伪代码：

sum = n, r = n, b = 1
while v ≠ r:
    d = (r - v) / b
    j = ν₂(d)       // d 的末尾零个数
    next = r - b × 2^j
    sum += next
    b ← b × 2^(j+1)
    r ← next
输出 sum

手动跑一下样例 9 6：

$r=9, b=1$ ： $d=3, j=0$ ，下一步 $8$ ， $b \leftarrow 2$ ，sum $=17$
$r=8, b=2$ ： $d=1, j=0$ ，下一步 $6$ ， $b \leftarrow 4$ ，sum $=23$
$r=6=v$ ，输出 $23$ ✓
时间复杂度 $O(\log n)$ ，完全可以处理 $10^{18}$ 。

AI 说的实在是，怎么说呢？讲的不是说很好啊，这 AI 讲的不是说很好，所以我认为真正的 AGI 啊，真正的 AGI 肯定是要会画图的。啊，现在的这个 AI 这个画图能力比较一言难尽吧。

哎，不扯了，我们来看看这道题目。这道题目的规律，我这样子画了一张图啊，我觉得就很明显了。这就是所谓 AI 口中的自相似。你要说是自相似也也没什么问题，但是呢，自相似，但又没有那么相似。首先要注意到，根节点的孩子是 N 减一、 N 减二、 N 减四、 N 减八、 N 减十六。云云。这个注意到还是有一定难度啊，还是有一定难度，因为他毕竟哎，毕竟他不是一个这个线性的规律，对吧？

然后你注意到这个规律以后呢，你可以把这个规律应用于下面的节点，它们的孩子节点是怎么样子的。我们会发现，如果说这个根节点是 N 减一，那么令 N 减一等于 N 那么它的叶子节点，它的孩子节点就是 N 撇减二、 N 撇减四、 N 撇减八。如果令 N 撇减二等于 N 撇撇。那么它的孩子节点就是 N 撇撇减四。

好，现在的问题就来到什么呢？你注意到了这个规律，要写一个程序，在 LogN 的时间复杂度内求解。

注意啊，就是减法非常难以考虑。你去减法的话，你就会发现，哎，他怎么退位呀，进位呀，反正反正很难考虑。但是不妨反过来想。我们是要判断一一个点，就这个数在哪棵子树内。那我们就想，它能不能通过某种方法去加到它的根，对吧？去加回到它的根。加法比减法好想的多。

究其原因呢，加法比减法好想，其实是因为减法它会影响其后面的位，加法只会影响它前面的位。减法的这种回退的特性是我们最讨厌的。

判断的逻辑如此书写即可。不难发现的，我们实际上就是想要查看后 CI +1 位它的这个是否一样。之所以查看的是后 CI 加一位，是因为加法它只能改变 CI 加二位以及以后的位，它的这个情况。

// 判断 V 属不属于 u,ci 的这个子树。
auto check=[&](ll u,ll ci) -> bool {
  // 查看后 CI +1 位它的这个是否一样，所需要的 mask。
    ll mask=(1ll<<(ci+1))-1;
    // 直接进行与运算以后，就得到了 V 的后 CI +1 位，以及 U 的后 CI +1 位。
    ll a=mask&V,b=mask&u;
    if (a==b) {
        return true;
    }
    return false;
};

有了这个 check 函数以后，我们就写一个递归式的 solve 函数，就可以非常轻松的求解这个东西了。

auto solve=[&](auto && self,ll u,ll ci) -> void {
    ans+=u;
    if (u==V) {
        return;
    }
    for (ll j=ci+1;;j++) {
        ll to=u-(1ll<<j);
        if (to<=0) {
            break;
        }
        // 下面我们就是要判断我们想求的 V 到底在哪个子树之中呢？
        // 严格来讲，其实是判断 V 属不属于 to 的这个子树。
        if (check(to,j)) {
            self(self,to,j);
            break;
        }
    }
};

AC代码

哎呀，这个 CF 挂的。今天是2月20号，这 CF 还是在，就是已经挂了5个多小时了。那么AI 我让 AI 对拍了一下这个程序是对的。啊，他拍了2000多组数据，都没发现这个 hack 那么这个应该就是对的。这个我这个也是一遍写出来的，挺爽的。

https://codeforces.com/gym/106169/submission/363673850

源代码

/**
 * Problem: I. Cutting Trees
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106169/problem/I
 * Created: 2026-02-19 23:02:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */
void Solve() {
    ll N,V;
    cin >> N >> V;
    ll ans=0;
    // 判断 V 属不属于 u,ci 的这个子树。
    auto check=[&](ll u,ll ci) -> bool {
        ll mask=(1ll<<(ci+1))-1;
        ll a=mask&V,b=mask&u;
        if (a==b) {
            return true;
        }
        return false;
    };
    auto solve=[&](auto && self,ll u,ll ci) -> void {
        ans+=u;
        if (u==V) {
            return;
        }
        for (ll j=ci+1;;j++) {
            ll to=u-(1ll<<j);
            if (to<=0) {
                break;
            }
            // 下面我们就是要判断我们想求的 V 到底在哪个子树之中呢？
            // 严格来讲，其实是判断 V 属不属于 to 的这个子树。
            if (check(to,j)) {
                self(self,to,j);
                break;
            }
        }
    };
    solve(solve,N,-1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

ITMO Academy pilot course » Segment Tree, part 1 » Step 3 » Practice（线段树综合应用，求逆序对，）

Posted on 2026-02-18 Edited on 2026-02-19

哎，感觉最近这个线段数的题目比较少啊，感觉再搓一个模板也没什么用。就再看吧，遇到线段数的题目我们再搓个模板好吧，遇到线段数的题目我们再搓模板，没遇到线段树的题目就不搓了啊。

题目 A. Inversions（求逆序对）

源代码

题目2

源代码

题目3

源代码

题目4

源代码

题目5

源代码

ITMO Academy pilot course » Segment Tree, part 1 » Step 2 » Practice（ITMO 线段树部分1，第2步的练习，单点修改线段树，线段树上二分）

Posted on 2026-02-18 Edited on 2026-02-19

题目1（单点修改、区间查询、最大子段和）

题目大意

给定一个长度为 $n$ 的数组 $a$ ，初始元素范围为 $-10^9 \le a_i \le 10^9$ 。你需要处理 $m$ 次操作，每次操作将索引 $i$ 处的元素修改为 $v$ 。

你需要输出 $m+1$ 行结果：

在所有操作之前，数组中最大子段和（连续子数组的最大和）。
在每次修改操作后，当前数组的最大子段和。

注意：

子段可以为空，空子段的和定义为 $0$ 。因此答案至少为 $0$ 。
$1 \le n, m \le 100000$ 。
索引 $i$ 从 $0$ 开始 ( $0 \le i < n$ )。

输入格式

第一行包含两个整数 $n$ 和 $m$ 。
第二行包含 $n$ 个整数，表示数组的初始状态。
接下来的 $m$ 行，每行包含两个整数 $i$ 和 $v$ ，表示将 $a_i$ 修改为 $v$ 。

输出格式

输出共 $m+1$ 行，每行一个整数，表示当前状态下的最大子段和。

样例 1

5 2
5 -4 4 3 -5
4 3
3 -1

样例 1 输出

1
2
3

8
11
7

样例 1 解释

初始状态：数组为 [5, -4, 4, 3, -5]。

最大子段和为 $5 + (-4) + 4 + 3 = 8$ （索引 $0$ 到 $3$ ）。
输出 8。

第一次操作 4 3：将 $a_4$ 修改为 $3$ 。

数组变为 [5, -4, 4, 3, 3]。
最大子段和为 $5 + (-4) + 4 + 3 + 3 = 11$ （索引 $0$ 到 $4$ ）。
输出 11。

第二次操作 3 -1：将 $a_3$ 修改为 $-1$ 。

数组变为 [5, -4, 4, -1, 3]。
最大子段和为 $5 + (-4) + 4 + (-1) + 3 = 7$ （索引 $0$ 到 $4$ ）。
输出 7。

样例 2

4 2
-2 -1 -5 -4
1 3
3 2

样例 2 输出

1
2
3

0
3
3

样例 2 解释

初始状态：数组全为负数 [-2, -1, -5, -4]，最大子段为空子段，和为 0。
第一次操作 1 3：数组变为 [-2, 3, -5, -4]，最大子段为 [3]，和为 3。
第二次操作 3 2：数组变为 [-2, 3, -5, 2]，最大子段仍为 [3]，和为 3。

我们的这个程序就是直接，Max 0LL去解决这个最小值不能小于0的这个问题。

AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363498742

源代码

/**
 * Problem: A. Segment with the Maximum Sum
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A
 * Created: 2026-02-18 18:23:03
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    ll l=0, r=0, pre_sum=0, suf_sum=0, mx_sum=0, sum=0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:"<<"mx_sum:"<<a.mx_sum;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l=a.l;
        res.r=b.r;
        res.sum=a.sum+b.sum;
        res.pre_sum=max(a.pre_sum,a.sum+b.pre_sum);
        res.suf_sum=max(b.suf_sum,a.suf_sum+b.sum);
        res.mx_sum=max({a.mx_sum,b.mx_sum,a.suf_sum+b.pre_sum});
        return res;
    }
};

template<class T>
struct SEG {
    ll N;
    vector<T> infos;

    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = T::merge(res, query(u << 1, l, r));
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            res = T::merge(res, query(u << 1 | 1, l, r));
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<Info> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i].sum;
        A[i].pre_sum=A[i].sum;
        A[i].suf_sum=A[i].sum;
        A[i].mx_sum=A[i].sum;
    }
    SEG seg(N,A);
    cout<<max(0ll,seg.query(1,1,N).mx_sum)<<"\n";
    for (int i=1;i<=M;++i) {
        ll pos,val;
        cin>>pos>>val;
        pos++;
        seg.assign(1,pos,{0,0,val,val,val,val});
        cout<<max(0ll,seg.query(1,1,N).mx_sum)<<"\n";
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363498742

*/

P4513 小白逛公园

https://www.luogu.com.cn/problem/P4513

就是这个线段数结构体初值的设定啊，就是 sum 类的一定要负0，不要负什么 inf infinite 这样的值。那么其实付出值并不能够比较好的保证这样子的一个结果。最好的保证结果的方法呢，还是就是不要使用初值去 merge 任何东西。最好就不要使用初值。初值是设定初值只是为了防止报错而已，最好就不要使用初值。

struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    ll l = 0, r = 0, pre_sum = 0, suf_sum = 0, mx_sum = 0, sum = 0;

AC
https://www.luogu.com.cn/record/263243648

源代码

/**
 * Problem: P4513 小白逛公园
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P4513
 * Created: 2026-02-18 18:37:49
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */


struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    ll l = 0, r = 0, pre_sum = 0, suf_sum = 0, mx_sum = 0, sum = 0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:" << "mx_sum:" << a.mx_sum;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l = a.l;
        res.r = b.r;
        res.sum = a.sum + b.sum;
        res.pre_sum = max(a.pre_sum, a.sum + b.pre_sum);
        res.suf_sum = max(b.suf_sum, a.suf_sum + b.sum);
        res.mx_sum = max({a.mx_sum, b.mx_sum, a.suf_sum + b.pre_sum});
        return res;
    }
};

template<class T>
struct SEG {
    ll N;
    vector<T> infos;

    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        bool isget=false;
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = query(u << 1, l, r);
            isget=true;
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            if (isget) {
                res = T::merge(res, query(u << 1 | 1, l, r));
            }else {
                res=query(u << 1 | 1, l, r);
            }
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<Info> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i].sum;
        A[i].pre_sum = A[i].sum;
        A[i].suf_sum = A[i].sum;
        A[i].mx_sum = A[i].sum;
    }
    SEG seg(N, A);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll l,r;
            cin>>l>>r;
            if (l>r) {
                swap(l,r);
            }
            cout<<seg.query(1,l,r).mx_sum<<"\n";
        }else {
            ll pos,val;
            cin>>pos>>val;
            seg.assign(1, pos, {0, 0, val, val, val, val});
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

题目2（找到第 K 个一）

这道题目一开始有点问题啊，是因为什么呢？是因为这个0 base 的和1 base 的这个转换转错了。

AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918

源代码

/**
 * Problem: B. K-th one
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/B
 * Created: 2026-02-18 21:21:00
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

/*
 * 2026-02-18: 测试这个线段树二分
 */
struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    ll l = 0, r = 0, sum = 0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:" << "sum:" << a.sum;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l = a.l;
        res.r = b.r;
        res.sum = a.sum + b.sum;
        return res;
    }
};

template<class T=Info>
struct SEG {
    ll N;
    vector<T> infos;

    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        bool isget=false;
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = query(u << 1, l, r);
            isget=true;
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            if (isget) {
                res = T::merge(res, query(u << 1 | 1, l, r));
            }else {
                res=query(u << 1 | 1, l, r);
            }
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    //  返回第k个有值的下标，当然，要求线段树叶节点值是0或1
    ll findkth(ll u,ll cur_k) {
        if (infos[u].l==infos[u].r) {
            return infos[u].l;
        }
        if (cur_k<=infos[u<<1].sum) {
            return findkth(u<<1,cur_k);
        }
        return findkth(u<<1|1,cur_k-infos[u<<1].sum);
    }

    void opposite(ll u, ll pos) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u].sum ^= 1;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            opposite(u << 1, pos);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            opposite(u << 1 | 1, pos);
        }
        pull(u);
    }
    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<Info> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i].sum;
    }
    SEG seg(N,A);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==2) {
            ll kth;
            cin>>kth;
            kth++;
            ll res=seg.findkth(1,kth);
            res--;
            cout<<res<<"\n";
        }else {
            ll pos;
            cin>>pos;
            pos++;
            seg.opposite(1,pos);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918

*/

题目3 C. First element at least X

题目挖了一发，是因为这个，即便在叶子节点啊，我们也要检查一下，然后再返回。虽然一般来说，我们进入叶子节点的时候，肯定是检查过的。但如果根节点本身就是叶子节点的话，我们可能未执行检查，所以导致错误。

ll findFirst(ll u,ll l,ll r,F && fun) {
    if (infos[u].l==infos[u].r) {
        if (fun(infos[u])) return infos[u].l;
        return -1;
    }
    ll res=-1;
    if (isIntersect(infos[u<<1].l, infos[u<<1].r, l, r) && fun(infos[u<<1])) {
        res=findFirst(u<<1,l,r,fun);
    }
    if (res!=-1) return res;
    if (isIntersect(infos[u<<1|1].l, infos[u<<1|1].r, l, r) && fun(infos[u<<1|1])) {
        res=findFirst(u<<1|1,l,r,fun);
    }
    return res;
}

AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363525477

源代码

/**
 * Problem: C. First element at least X
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C
 * Created: 2026-02-18 22:28:50
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */
/*
 * 2026-02-18: 测试这个线段树二分（找到第 K 个 1）
 * https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918
 */
struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    ll l = 0, r = 0, mx = 0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:" << "mn:" << a.mx;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l = a.l;
        res.r = b.r;
        res.mx = max(a.mx,b.mx);
        return res;
    }
};

template<class T=Info>
struct SEG {
    ll N;
    vector<T> infos;

    static bool isIntersect(ll l1,ll r1,ll l2,ll r2) {
        if (!(l1>r2 || r1<l2)) return true;
        return false;
    }
    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        bool isget=false;
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = query(u << 1, l, r);
            isget=true;
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            if (isget) {
                res = T::merge(res, query(u << 1 | 1, l, r));
            }else {
                res=query(u << 1 | 1, l, r);
            }
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    //  返回第k个有值的下标，当然，要求线段树叶节点值是0或1
    // ll findkth(ll u,ll cur_k) {
    //     if (infos[u].l==infos[u].r) {
    //         return infos[u].l;
    //     }
    //     if (cur_k<=infos[u<<1].sum) {
    //         return findkth(u<<1,cur_k);
    //     }
    //     return findkth(u<<1|1,cur_k-infos[u<<1].sum);
    // }
    //
    // void opposite(ll u, ll pos) {
    //     if (infos[u].l == infos[u].r && infos[u].l == pos) {
    //         infos[u].sum ^= 1;
    //         return;
    //     }
    //     if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
    //         opposite(u << 1, pos);
    //     }
    //     if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
    //         opposite(u << 1 | 1, pos);
    //     }
    //     pull(u);
    // }
    template<class F>
    ll findFirst(ll u,ll l,ll r,F && fun) {
        if (infos[u].l==infos[u].r) {
            if (fun(infos[u])) return infos[u].l;
            return -1;
        }
        ll res=-1;
        if (isIntersect(infos[u<<1].l, infos[u<<1].r, l, r) && fun(infos[u<<1])) {
            res=findFirst(u<<1,l,r,fun);
        }
        if (res!=-1) return res;
        if (isIntersect(infos[u<<1|1].l, infos[u<<1|1].r, l, r) && fun(infos[u<<1|1])) {
            res=findFirst(u<<1|1,l,r,fun);
        }
        return res;
    }
    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<Info> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i].mx;
    }
    SEG seg(N,A);

    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll pos,val;
            cin >> pos >> val;
            pos++;
            seg.assign(1, pos, {0,0,val});
        }else {
            ll val;
            cin>>val;
            auto fun=[&](const Info &a) -> bool {
                if (a.mx>=val) {
                    return true;
                }
                return false;
            };
            ll res=seg.findFirst(1,1,N,fun);
            if (res==-1) {
                cout<<res<<"\n";
                continue;
            }
            res--;
            cout<<res<<"\n";
        }
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363525477

*/

题目4 D. First element at least X - 2

那么其实啊，上一题目的代码里面，我已经采用了可以通过这道题目的实现。

AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363527109

源代码

/**
 * Problem: D. First element at least X - 2
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/D
 * Created: 2026-02-18 23:09:01
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */


/*
 * 2026-02-18: 测试这个线段树二分（找到第 K 个 1）
 * https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918
 * 2026-02-18: 测试线段树二分（找到 ≥ val 的第一个下标）
 * https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363527109
 */
struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    ll l = 0, r = 0, mx = 0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:" << "mn:" << a.mx;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l = a.l;
        res.r = b.r;
        res.mx = max(a.mx,b.mx);
        return res;
    }
};

template<class T=Info>
struct SEG {
    ll N;
    vector<T> infos;

    static bool isIntersect(ll l1,ll r1,ll l2,ll r2) {
        if (!(l1>r2 || r1<l2)) return true;
        return false;
    }
    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        bool isget=false;
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = query(u << 1, l, r);
            isget=true;
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            if (isget) {
                res = T::merge(res, query(u << 1 | 1, l, r));
            }else {
                res=query(u << 1 | 1, l, r);
            }
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    //  返回第k个有值的下标，当然，要求线段树叶节点值是0或1
    // ll findkth(ll u,ll cur_k) {
    //     if (infos[u].l==infos[u].r) {
    //         return infos[u].l;
    //     }
    //     if (cur_k<=infos[u<<1].sum) {
    //         return findkth(u<<1,cur_k);
    //     }
    //     return findkth(u<<1|1,cur_k-infos[u<<1].sum);
    // }
    //
    // void opposite(ll u, ll pos) {
    //     if (infos[u].l == infos[u].r && infos[u].l == pos) {
    //         infos[u].sum ^= 1;
    //         return;
    //     }
    //     if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
    //         opposite(u << 1, pos);
    //     }
    //     if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
    //         opposite(u << 1 | 1, pos);
    //     }
    //     pull(u);
    // }

    template<class F>
    ll findFirst(ll u,ll l,ll r,F && fun) {
        if (infos[u].l==infos[u].r) {
            if (fun(infos[u])) return infos[u].l;
            return -1;
        }
        ll res=-1;
        if (isIntersect(infos[u<<1].l, infos[u<<1].r, l, r) && fun(infos[u<<1])) {
            res=findFirst(u<<1,l,r,fun);
        }
        if (res!=-1) return res;
        if (isIntersect(infos[u<<1|1].l, infos[u<<1|1].r, l, r) && fun(infos[u<<1|1])) {
            res=findFirst(u<<1|1,l,r,fun);
        }
        return res;
    }
    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<Info> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i].mx;
    }
    SEG seg(N,A);

    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll pos,val;
            cin >> pos >> val;
            pos++;
            seg.assign(1, pos, {0,0,val});
        }else {
            ll val,l;
            cin>>val>>l;
            l++;
            auto fun=[&](const Info &a) -> bool {
                if (a.mx>=val) {
                    return true;
                }
                return false;
            };
            ll res=seg.findFirst(1,l,N,fun);
            if (res==-1) {
                cout<<res<<"\n";
                continue;
            }
            res--;
            cout<<res<<"\n";
        }
    }
    
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363527109

*/

ITMO Academy pilot course » Segment Tree, part 1 » Step 1 » Practice（ITMO 线段树部分一，第1步的练习，单点修改线段树）

Posted on 2026-02-18

题目一（普通的单点修改、区间和查询线段树）

题目描述

需要编写一个标准的线段树来维护数组的区间和，支持单点修改和区间求和操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ ( $1 \le n, m \le 100000$ )，分别表示数组的大小和操作的次数。
第二行包含 $n$ 个整数 $a_i$ ，表示数组的初始状态 ( $0 \le a_i \le 10^9$ )。
接下来的行包含操作的描述。每个操作的描述如下：

1 i v：将索引为 $i$ 的元素设置为 $v$ ( $0 \le i < n$ , $0 \le v \le 10^9$ )。
2 l r：计算索引从 $l$ 到 $r-1$ 的元素之和 ( $0 \le l < r \le n$ )。

输出格式

对于每个第二种类型的操作，打印对应的和。

样例输入

样例输出

1
2
3

11
8
14

样例解释

初始数组为 [5, 4, 2, 3, 5]（注意题目中下标从 0 开始）。

操作 2 0 3：计算下标 $[0, 3)$ 即 $0, 1, 2$ 的和。 $5 + 4 + 2 = 11$ 。
操作 1 1 1：将下标为 1 的元素修改为 1。数组变为 [5, 1, 2, 3, 5]。
操作 2 0 3：再次计算下标 $[0, 3)$ 的和。 $5 + 1 + 2 = 8$ 。
操作 1 3 1：将下标为 3 的元素修改为 1。数组变为 [5, 1, 2, 1, 5]。
操作 2 0 5：计算下标 $[0, 5)$ 即整个数组的和。 $5 + 1 + 2 + 1 + 5 = 14$ 。

AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363403398

源代码

/**
 * Problem: A. Segment Tree for the Sum
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A
 * Created: 2026-02-17 20:50:46
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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, testcase;

/*
 *
 */
struct Info {
    ll l,r,sum;
    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]";
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }
};
Info merge(const Info &a,const Info &b) {
    return {a.l,b.r,a.sum+b.sum};
}
struct SEG {
    ll N;
    vector<Info> infos;
    SEG(ll N,const vector<Info> &a) {
        infos.resize(4*N+5);
        this->N=N;
        build(a,1,1,N);
    }
    void pull(ll u) {
        infos[u]=merge(infos[u<<1],infos[u<<1|1]);
    }
    void build(const vector<Info> &a,ll u,ll l,ll r) {
        if (l==r) {
            infos[u]=a[l];
            infos[u].l=l;
            infos[u].r=r;
            return;
        }
        ll mid=l+r>>1;
        build(a,u<<1,l,mid);
        build(a,u<<1|1,mid+1,r);
        pull(u);
    }
    Info query(ll u,ll l,ll r) {
        if (infos[u].l>=l && infos[u].r<=r) {
            return infos[u];
        }
        Info res{};
        if (!(infos[u<<1].r<l || infos[u<<1].l>r)) {
            res=merge(res,query(u<<1,l,r));
        }
        if (!(infos[u<<1|1].r<l || infos[u<<1|1].l>r)) {
            res=merge(res,query(u<<1|1,l,r) );
        }
        return res;
    }
    void assign(ll u,ll pos,const Info &val) {
        if (infos[u].l==infos[u].r && infos[u].l==pos) {
            infos[u]=val;
            infos[u].l=pos;
            infos[u].r=pos;
            return;
        }
        if (pos>=infos[u<<1].l && pos<=infos[u<<1].r) {
            assign(u<<1,pos,val);
        }
        if (pos>=infos[u<<1|1].l && pos<=infos[u<<1|1].r) {
            assign(u<<1|1,pos,val);
        }
        pull(u);
    }
/*
 *AC https://codeforces.com/gym/106169/submission/363483057
 *线段树可视化 AC 记录
 */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back()==' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i=1;i<=mx_layer;++i) {
            if (layer+i>mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        // grid[layer + 1][sc + widths[u << 1] + 1] = '|';
        // if (layer+2 <= mx_layer) {
        //     grid[layer+2][sc + widths[u << 1] + 1]='|';
        // }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<Info> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i].sum;
    }
    SEG seg(N,A);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll pos,x;
            cin>>pos>>x;
            pos++;
            seg.assign(1,pos,{0,0,x});
        }else {
            ll l,r;
            cin>>l>>r;
            l++,r++;
            cout<<seg.query(1,l,r-1).sum<<"\n";
        }
    }
#ifdef LOCAL
    seg.visualize();
#endif

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363403398

*/

题目 2（单点修改，区间最小值查询线段树）

引入了这个泛型设计。就是假如以后可能有多个 info 的话，可以使用自动模板推导。

AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363486196

源代码

/**
 * Problem: B. Segment Tree for the Minimum
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/B
 * Created: 2026-02-18 16:08:21
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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, testcase;

/*
 *
 */
struct Info {
    // 注意啊，这里这个 MN 记得设一个初值。
    ll l, r, mn=INF;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:"<<a.mn;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        return {a.l, b.r, min(a.mn,b.mn)};
    }
};

template<class T>
struct SEG {
    ll N;
    vector<T> infos;

    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = T::merge(res, query(u << 1, l, r));
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            res = T::merge(res, query(u << 1 | 1, l, r));
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<Info> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i].mn;
    }
    SEG seg(N, A);

    for (int i = 1; i <= M; ++i) {
// #ifdef LOCAL
//         seg.visualize();
// #endif
        ll op;
        cin >> op;
        if (op == 1) {
            ll pos, x;
            cin >> pos >> x;
            pos++;
            seg.assign(1, pos, {0, 0, x});
        } else {
            ll l, r;
            cin >> l >> r;
            l++, r++;
            cout << seg.query(1, l, r - 1).mn << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363486196

*/

题目3（单点修改、区间最小值查询以及区间最小值个数查询线段树）

只需要设计一个新的 merge 函数即可。

static Info merge(const Info &a, const Info &b) {
    Info res;
    res.l=a.l;
    res.r=b.r;
    res.mn=min(a.mn,b.mn);
    if (a.mn==b.mn) {
        res.cnt=a.cnt+b.cnt;
    }else if (a.mn<b.mn) {
        res.cnt=a.cnt;
    }else {
        res.cnt=b.cnt;
    }
    return res;
}

AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363488027

源代码

/**
 * Problem: C. Number of Minimums on a Segment
 * Contest: ITMO Academy: pilot course
 * Judge: Codeforces
 * URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C
 * Created: 2026-02-18 16:36:09
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    ll l=0, r=0, mn=INF,cnt=0;

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:"<<"mn:"<<a.mn<<" cnt:"<<a.cnt;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l=a.l;
        res.r=b.r;
        res.mn=min(a.mn,b.mn);
        if (a.mn==b.mn) {
            res.cnt=a.cnt+b.cnt;
        }else if (a.mn<b.mn) {
            res.cnt=a.cnt;
        }else {
            res.cnt=b.cnt;
        }
        return res;
    }
};

template<class T>
struct SEG {
    ll N;
    vector<T> infos;

    SEG(ll N, const vector<T> &a) {
        infos.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void pull(ll u) {
        infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<T> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    T query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        T res{};
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = T::merge(res, query(u << 1, l, r));
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            res = T::merge(res, query(u << 1 | 1, l, r));
        }
        return res;
    }

    void assign(ll u, ll pos, const T &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    vector<ll> visual_widths;
    vector<string> visual_grid;
    ll mx_layer = 0;

    void visualize() {
        visual_widths.resize(4 * N + 2);
        cal_visual_w(1, 1);
        visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
        visualize(1, 0, 1);
        for (int i = 1; i <= mx_layer; ++i) {
            while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
                visual_grid[i].pop_back();
            }
            cerr << visual_grid[i] << "\n";
        }
    }

    void cal_visual_w(ll u, ll layer) {
        mx_layer = max(mx_layer, layer);
        if (infos[u].l == infos[u].r) {
            visual_widths[u] = infos[u].to_string().size();
            return;
        }
        cal_visual_w(u << 1, layer + 1);
        visual_widths[u] = visual_widths[u << 1] + 3;
        cal_visual_w(u << 1 | 1, layer + 1);
        visual_widths[u] += visual_widths[u << 1 | 1];
    }

    // 可视化线段树
    void visualize(ll u, ll sc, ll layer) {
        if (infos[u].l == infos[u].r) {
            string label = infos[u].to_string();
            for (ll i = 0; i < label.size(); ++i) {
                visual_grid[layer][sc + i] = label[i];
            }
            return;
        }
        visualize(u << 1, sc, layer + 1);
        string label = infos[u].to_string();
        ll pos = label.find(';');
        ll labStart = sc + visual_widths[u << 1] + 1 - pos;
        for (int i = 1; i <= mx_layer; ++i) {
            if (layer + i > mx_layer) break;
            visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
        }
        for (ll i = 0; i < label.size(); ++i) {
            visual_grid[layer][labStart + i] = label[i];
        }
        visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
    }
#endif
};

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<Info> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i].mn;
        A[i].cnt=1;
    }
    SEG seg(N, A);

    for (int i = 1; i <= M; ++i) {
        // #ifdef LOCAL
        //         seg.visualize();
        // #endif
        ll op;
        cin >> op;
        if (op == 1) {
            ll pos, x;
            cin >> pos >> x;
            pos++;
            seg.assign(1, pos, {0, 0, x, 1});
        } else {
            ll l, r;
            cin >> l >> r;
            l++, r++;
            auto res=seg.query(1, l, r - 1);
            cout << res.mn<<" "<<res.cnt << "\n";
        }
    }
    
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363488027

*/