$Q\ \le\ 2\times 10^5$ で解けるの凄い！

## 問題概要

https://atcoder.jp/contests/abc237/tasks/abc237_g

長さ$N$の順列$P$を与えます。以下の$Q$個のクエリを処理します。

クエリ`t l r`
- $t = 1$ならば、$P_{l}, P_{l + 1}, \dots, P_{r - 1}, P_{r}$を昇順にソートする
- $t = 2$ならば、$P_{l}, P_{l + 1}, \dots, P_{r - 1}, P_{r}$を降順にソートする

すべてのクエリを処理した後、$P_i = X$を満たす$i$を報告してください

#### 制約

$1\ \le\ N, Q\ \le\ 2\times 10^5$

## 情報を削る・観察

普通にクエリを処理するのは難しいと感じました。[^1]

最終的に$P_i = X$を満たす$i$が求まれば良いことを念頭に、クエリにおいてそのような$i$がどう移動するかを観察します。

- 区間に該当する$i$が含まれていない場合
- 移動しない
- 区間に$i$が含まれている時
- 昇順ソートの場合、その区間に含まれる$X$よりも小さい値より後ろに移動する。また、その区間に含まれる$X$より大きい値より前に移動する
- 降順ソートの場合、反対になる(大きい値の後ろ、小さい値の前に移動する)

よって、各値が$X$より小さい/等しい/大きいかのみが重要であることがわかります。

ここから、順列では無く、以下の数列$P'$上でクエリを処理します。

$$P'_i =
\begin{cases}
-1 & \text{if}\ P_i < X \\
0 & \text{if}\ P_i = X \\
1 & \text{else}
\end{cases}$$

## P'上でのクエリ処理

観察で見た通り、クエリ処理では区間に含まれる$X$より小さい数と区間に含まれる$X$より大きい数が重要でした。$P'$上ではこれを「区間に含まれる$-1$の数」と「区間に含まれる$1$の数」と言い換えることができます
- このような数を求めるのは累積和等でできますね。実際はクエリ処理で要素の移動が発生するので、今回はセグメント木等の値の変更に強いデータ構造を利用することになります。

クエリの区間に含まれる$-1$の数を$a$、$0$の数を$b$、$1$の数を$c$とします。[^2]

クエリが昇順ソートだった場合、区間$P_l, P_{l + 1}, \dots, P_{r - 1}, P_{r}$は$P_l, P_{l + 1}, \dots, P_{l + a}$は$-1$、$P_{l + a + 1}, \dots, P_{l + a + b}$は$0$、$P_{l + a + b}, \dots, P_{l + a + b + c = r}$は$1$になります。このような数列の変更は、Range Update Queryを$3$回行えば実現することが可能です。

降順ソートだった場合も同様に考えることができます。

以上により、例えば遅延セグメント木を利用する事で$P'$上のクエリ処理が実現することができました。

## 提出コード

自分の遅延セグ木、RUQライブラリがかなりお粗末だった。

using tup = tuple<i32, i32, i32>;
 
tup operator+(const tup& a, const tuple<i32, i32, i32>& b) {
    auto [x, y, z] = a;
    auto [p, q, r] = b;
    return tup{ x + p, y + q, z + r };
}
 
tup operator*(i32 k, const tup& a) {
    auto [x, y, z] = a;
    return tup{ k * x, k * y, k * z };
}
 
using vM = zawa::rangeAddMonoid<tuple<i32, i32, i32>>;
 
struct oM {
    using valueType = tuple<i32, i32, i32>;
    static constexpr valueType identity{ -1, -1, -1 };
    static valueType operation([[maybe_unused]] const valueType& a, const valueType& b) {
        return b;
    }
};
 
struct action {
    using valueMonoid = vM;
    using operatorMonoid = oM;
    static valueMonoid::valueType mapping(const valueMonoid::valueType& a, const tuple<i32, i32, i32>& b) {
        return valueMonoid::valueType{ a.size * b, a.size };
    }
};
 
void main_() {
    i32 N, Q, X; in(N, Q, X);
    vector<vM::valueType> init(N);
    tuple<i32, i32, i32> pls = { 0, 0, 1 }, mns = { 1, 0, 0 }, eq = { 0, 1, 0 };
    for (i32 i = 0 ; i < N ; i++) {
        i32 p; in(p);
        init[i].size = 1;
        if (p < X) init[i].value = mns;
        if (p == X) init[i].value = eq;
        if (p > X) init[i].value = pls;
    }
    zawa::lazySegmentTree<action> S(init);
    times(Q) {
        i32 c, l, r; in(c, l, r);
        l--;
        if (c == 1) {
            auto [m, e, p] = S.prod(l, r).value;
            assert(l + m + e + p == r);
            S.update(l, l + m, mns);
            S.update(l + m, l + m + e, eq);
            S.update(l + m + e, l + m + e + p, pls);
        }
        else if (c == 2) {
            auto [m, e, p] = S.prod(l, r).value;
            assert(l + m + e + p == r);
            S.update(l, l + p, pls);
            S.update(l + p, l + p + e, eq);
            S.update(l + p + e, l + p + e + m, mns);
        }
        else {
            assert(!"input failed");
        }
    }
    i32 ans = -1;
    for (i32 i{} ; i <= N ; i++) if (get<1>(S.prod(0, i).value) == 1) {
        ans = i;
        break;
    }
    out(ans);
}

[^1]: Library Checkerに区間ソートをする問題がありますが、自分はよくわかってないです。[問題](https://judge.yosupo.jp/problem/point_set_range_sort_range_composite)

[^2]: $b$は$0$か$1$のどちらかとなります