はまやんはまやんはまやん

hamayanhamayan's blog

Sorted? [yukicoder 905]

https://yukicoder.me/problems/no/905

解説

https://yukicoder.me/submissions/389294

ある列が広義単調増加列であるというのは、各要素間でA[i]≦A[i+1]であればいい。
A[i]≦A[i+1]であるなら1、そうでないなら0であるとすると、すべての要素間が1であればいい。
これはこの区間についての総積が1であればいいことに言い換えられる。
よって、事前に隣接する要素についてA[i]≦A[i+1]であるかを見て、区間積をとるセグメントツリーを作ればいい。
あとは、これを使って、答えていく。

広義単調減少であるかの判定も全く同じように行う。

int N; ll A[101010];
SegTree<int, 1 << 17> stup, stdwn;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N - 1) {
        if (A[i] <= A[i + 1]) stup.update(i, 1);
        else stup.update(i, 0);

        if (A[i] >= A[i + 1]) stdwn.update(i, 1);
        else stdwn.update(i, 0);
    }

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int l, r; cin >> l >> r;
        
        int f = stup.get(l, r);
        int g = stdwn.get(l, r);

        printf("%d %d\n", f, g);
    }
}