ABC237-G Range Sort Query

これ で解けるのすごいね......

問題概要

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

長さの順列を与えます。以下のクエリを回処理します。

クエリ・・・を与える。順列の番目の要素から番目の要素までについてなら昇順にソート、なら降順にソートする

すべてのクエリを処理した後、を満たすを出力しなさい

制約

情報を削る

普通にクエリを処理するのはどう頑張っても無理だと感じた*1

であるが最終的に求まれば良いので、元のクエリ処理と等価なものでもっと簡単なクエリ処理が存在しないかを考えた。

区間ソートクエリにおいて、であるがどのように移動するかを観察する。

• 区間にが含まれてない時・・・・移動しない
• 区間にが含まれている時・・・・その区間に含まれるよりも小さい要素の数とよりも大きい要素の数に依存する

なので、各要素がであるか、より小さい要素であるか、大きい要素であるかのみが重要であることがわかる。　

なので順列から以下のような列を考えることにする。

• (がよりも小さい時
• (の時
• (がよりも大きい時

上でのクエリ処理

であるが移動する時は、クエリに含まれるより小さい/大きい要素の数に依存するので、区間に含まれる、である要素の数を数えられるようにする必要がある

• これはRSQですね！

ソート自体はどう実現するかを考える。

例えば を昇順にソートすると になる

区間に含まれるの数をとして、番目の要素はになることがわかる。

については、の含まれる数をとして*2番目の要素ははならになることがわかる

についても似たように考えることができる。

これらはRUQを、、それぞれについてRUQを適用すれば実現できる　<- !!!!!

提出コード

自分の遅延セグ木、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:https://judge.yosupo.jp/problem/point_set_range_sort_range_composite Library Checkerに区間ソートクエリあってビビってる。マジかよ

*2:はかですね