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); } }