参考にした実装 https://blog.hamayanhamayan.com/entry/2021/07/24/203450
全ての \(j\) を求めるとあるが，まずは \(1\) 個求める． 特に，最小の \(j_{0}\) を求められれば， \(j_{0}+1\) 以降の中から 最小の \(j_{1}\) を求めることができる． これを繰り返して全ての \(j\) を求められる
ペア \((a_{i}, i)\) に対してsegtreeを考えれば， 最小の \(a_{i}\) が複数あった場合に， \(i\)が最小のものが手に入る．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
//---------------------------------------------------------------------------------------------------
pll op(pll a, pll b){
return min(a,b);
}
pll e(){
return {INFL, 0};
}
//---------------------------------------------------------------------------------------------------
int main() {
ll n, q;
cin >> n >> q;
vll a(n); rep(i,n) { cin >> a[i]; }
segtree<pll, op, e> st(n+5);
rep(i,n){
st.set(i, {a[i], i});
}
rep(qi,q){
ll t, x,y; cin >> t >> x >> y;
--x;
if(t == 1){
st.set(x, {y, x});
}else{
pll mi = st.prod(x,y);
ll p = mi.first;
ll i = mi.second;
vll ans;
ans.push_back(i);
while(true){
pll t = st.prod(i+1,y);
if(t.first != p) break;
i = t.second;
ans.push_back(i);
}
cout << ans.size() << " ";
for(auto k:ans){
cout << k+1 << " ";
}
cout << endl;
}
}
return 0;
}
