Solution
题目来源：AT_past202107_l（in AtCoder | in luogu）
用线段树维护区间最小值。单点修改很好写，我们看怎么区间寻找最小值位置。
对于每次询问，我们先求出所查询区间 \([x_i, y_i]\) 的最小值 \(p\)，然后写一个寻找函数。对于当前区间 \([l, r]\)，分以下情况来看：
- 如果当前区间长度 \(> 1\)、并且并不包含在所查询区间内（即 \(l < x_i\) 或 \(r > y_i\)），我们像正常线段树一样递归查找其在所查询区间内的左右子区间。
- 如果当前区间长度 \(> 1\)、并且在查询区间内（即 \(x_i \le l\) 且 \(r \le y_i\)），则该区间的最小值至少为 \(p\)。我们递归寻找其最小值为 \(p\) 的左右子区间即可。
- 如果当前区间长度恰为 \(1\)，则若当前位置的数是 \(p\)，则该位置为答案，统计起来。
这部分代码如下：
void fnd(int l, int r, int k, int L, int R, ll x) {
if(l == r) {
if(minn[k] == x) v.push_back(l);
return;
}
int mid = (l + r) >> 1;
if(L <= l && r <= R) {
if(minn[ls(k)] == x) fnd(l, mid, ls(k), L, R, x);
if(minn[rs(k)] == x) fnd(mid + 1, r, rs(k), L, R, x);
return;
}
if(L <= mid) fnd(l, mid, ls(k), L, R, x);
if(mid < R) fnd(mid + 1, r, rs(k), L, R, x);
}
为啥情况 \(3\) 要加粗「当前位置的数是 \(p\)」呢？我们可以发现，存在查询区间 \([x_i, y_i]\) 与当前区间 \([l, r]\) 仅交于一个数的情况。这样递归下去会发现，我们最后递归到了那个相交的位置，但这个位置却不一定是 \(p\)。所以我们要特判一下。
不过这个递归过程还是有点麻烦了，可以参考 @SamHH0902 的实现方式。虽然我感觉我的更好想一点。
建议参考代码理解。code：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ls(a) ((a) << 1)
#define rs(a) ((a) << 1 | 1)
using namespace std;
#define ll long long
#define INF 2e9
const int N = 200010;
int n, q;
ll a[N];
ll minn[N * 4];
vector<ll> v;
void pushup(int k) {
minn[k] = min(minn[ls(k)], minn[rs(k)]);
}
void build(int l, int r, int k) {
minn[k] = INF;
if(l == r) {
minn[k] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls(k)), build(mid + 1, r, rs(k));
pushup(k);
}
void upd(int l, int r, int k, int x, ll c) {
if(l == r) {
minn[k] = c;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) upd(l, mid, ls(k), x, c);
else upd(mid + 1, r, rs(k), x, c);
pushup(k);
}
ll query(int l, int r, int k, int L, int R) {
if(L <= l && r <= R) {
return minn[k];
}
int mid = (l + r) >> 1; ll res = INF;
if(L <= mid) res = min(res, query(l, mid, ls(k), L, R));
if(mid < R) res = min(res, query(mid + 1, r, rs(k), L, R));
return res;
}
void fnd(int l, int r, int k, int L, int R, ll x) {
if(l == r) {
if(minn[k] == x) v.push_back(l);
return;
}
int mid = (l + r) >> 1;
if(L <= l && r <= R) {
if(minn[ls(k)] == x) fnd(l, mid, ls(k), L, R, x);
if(minn[rs(k)] == x) fnd(mid + 1, r, rs(k), L, R, x);
return;
}
if(L <= mid) fnd(l, mid, ls(k), L, R, x);
if(mid < R) fnd(mid + 1, r, rs(k), L, R, x);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
build(1, n, 1);
while(q--) {
int op; scanf("%d", &op);
if(op == 1) {
int x, y; scanf("%d%d", &x, &y);
upd(1, n, 1, x, y);
} else {
int l, r; scanf("%d%d", &l, &r);
v.clear();
ll m = query(1, n, 1, l, r);
fnd(1, n, 1, l, r, m);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
printf("%d ", (int) v.size());
for (int i = 0; i < (int)v.size(); i++) printf("%lld ", v[i]);
printf("\n");
}
}
return 0;
}