Day \(\mathbb{P}_9\)。
如果有权值为 \(0\) 的边，用所有这样的边把环分成若干条链。
不难发现若起始点在链的一端，先手必胜当且仅当链长（边数）为奇数。可以进行归纳证明，这种情况下先手每次移动必将边权置为 \(0\)。
继续推性质：
- 起始点在长度为奇数的链（奇链）上，那么删掉这个点后，这条链将会分成两个链，总恰好有其中一个链的长度为奇数，所以先手往那条链走并将走过的边权置为 \(0\) 即可。先手必胜。
- 起始点在长度为偶数的链（偶链）上，那么删掉这个点后，剩下两条链长度要不同时是奇数要不同时是偶数。根据前面的结论，奇数时先手必胜，偶数时后手必胜。
- 起始点在长度为奇环上，先手随便走一步并将边权置为 \(0\)，后手操作时相当于偶链的情况，于是先手必胜。
- 起始点在长度为偶环上，若先手直接将一条边权值置为 \(0\)，后手操作相当于奇链的情况，此时后手必胜。所以先手尽量不会将边权置为 \(0\)，不难得到两者策略均为走同一个方向，每次将边权 \(-1\)。由于是偶环，必定存在一个时刻，使得所有边权都减去了原来的边权最小值，即被分成若干的链，而棋子停留在起始点。所以先手必胜当且仅当此时状态下先手必胜。
所以线段树维护区间最小值、区间长度、区间最左侧的最小值到区间左端点的长度、区间最右侧最小值到区间右端点的长度、区间被最小值分割后每个段中（不包括两边，下同）奇数长度的段的长度 \(+1\) 总和、区间内被最小值分割后每个段中偶数长度的段的长度总和除以 \(2\) 即可。复杂度 \(O(q\log m)\)。
// Problem: P9546 [湖北省选模拟 2023] 山路长环 / ring
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9546
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Med;
const int N = 3e5 + 300;
int n, q, a[N];
struct node {
int mn, le, lt, rt, vo, ve;
node () : mn(0), le(0), lt(0), rt(0), vo(0), ve(0) { }
node (int x) : mn(x), le(1), lt(0), rt(0), vo(0), ve(0) { }
node operator + (const node &rh) const {
node res;
res.mn = min(mn, rh.mn), res.le = le + rh.le;
if (mn == res.mn) res.lt = lt, res.vo = vo, res.ve = ve;
else res.lt = le + rh.lt;
if (rh.mn == res.mn) res.rt = rh.rt, res.vo += rh.vo, res.ve += rh.ve;
else res.rt = rh.le + rt;
if (mn == res.mn && rh.mn == res.mn) {
if ((rt + rh.lt) & 1) res.vo += rt + rh.lt + 1;
else res.ve += (rt + rh.lt) >> 1;
}
return res;
}
} tr[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void upd(int l, int r, int p, int c, int x) {
if (l == r) return tr[x] = node(c), void();
if (p <= mid) upd(l, mid, p, c, ls);
else upd(mid + 1, r, p, c, rs);
tr[x] = tr[ls] + tr[rs];
}
node qry(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return tr[x];
if (s > mid) return qry(mid + 1, r, s, t, rs);
else if (t <= mid) return qry(l, mid, s, t, ls);
return qry(l, mid, s, t, ls) + qry(mid + 1, r, s, t, rs);
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i], upd(1, n, i, a[i], 1);
while (q--) {
int op, x, y; cin >> op >> x >> y;
if (op == 1) upd(1, n, x, y, 1);
else {
node res = qry(1, n, x, y, 1);
if (res.mn != 0 && ((y - x + 1) & 1)) cout << y - x + 1 << '\n';
else {
int ans = res.ve + res.vo;
if ((res.lt + res.rt) & 1) ans += res.lt + res.rt + 1;
else ans += (res.lt + res.rt) >> 1;
cout << ans << '\n';
}
}
}
}
bool Mbe;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Med - &Mbe) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}