ITMO Academy pilot course » Segment Tree, part 1 » Step 2 » Practice（ITMO 线段树部分1，第2步的练习，单点修改线段树，线段树上二分） · znzryb
## 题目1（单点修改、区间查询、最大子段和）
**题目大意**
给定一个长度为 $n$ 的数组 $a$，初始元素范围为 $-10^9 \le a_i \le 10^9$。你需要处理 $m$ 次操作，每次操作将索引 $i$ 处的元素修改为 $v$。
**你需要输出** $m+1$ **行结果**：
1. 在所有操作之前，数组中**最大子段和**（连续子数组的最大和）。
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 输出**
```
8
11
7
```
**样例 1 解释**
1. **初始状态**：数组为 `[5, -4, 4, 3, -5]`。
- 最大子段和为 $5 + (-4) + 4 + 3 = 8$（索引 $0$ 到 $3$）。
- 输出 `8`。
1. **第一次操作** `4 3`：将 $a_4$ 修改为 $3$。
- 数组变为 `[5, -4, 4, 3, 3]`。
- 最大子段和为 $5 + (-4) + 4 + 3 + 3 = 11$（索引 $0$ 到 $4$）。
- 输出 `11`。
1. **第二次操作** `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 输出**
```
0
3
3
```
**样例 2 解释**
1. **初始状态**：数组全为负数 `[-2, -1, -5, -4]`，最大子段为空子段，和为 `0`。
1. **第一次操作** `1 3`：数组变为 `[-2, 3, -5, -4]`，最大子段为 `[3]`，和为 `3`。
1. **第二次操作** `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](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363498742)
::: 源代码
```cpp
/**
* 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](https://www.luogu.com.cn/problem/P4513)
就是这个线段数结构体初值的设定啊，就是 sum 类的一定要负0，不要负什么 inf infinite 这样的值。那么其实付出值并不能够比较好的保证这样子的一个结果。最好的保证结果的方法呢，还是就是不要使用初值去 merge 任何东西。最好就不要使用初值。初值是设定初值只是为了防止报错而已，最好就不要使用初值。
```cpp
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](https://www.luogu.com.cn/record/263243648)
::: 源代码
```cpp
/**
* 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](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918)
::: 源代码
```cpp
/**
* 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
题目挖了一发，是因为这个，即便在叶子节点啊，我们也要检查一下，然后再返回。虽然一般来说，我们进入叶子节点的时候，肯定是检查过的。但如果**根节点本身就是叶子节点**的话，我们可能**未执行检查**，所以导致错误。
```cpp
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](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363525477)
::: 源代码
```cpp
/**
* 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](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363527109)
::: 源代码
```cpp
/**
* 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
*/
```
:::