Chef and Subarray Queries [CodeChef November Challenge 2017 F]

https://www.codechef.com/NOV17/problems/CSUBQ

N個の配列Aがあり、以下のクエリに答える。

• 「1 x y」 x番目の要素をyにする
• 「2 l r」 部分列[l,r]の中の任意の部分列の最大値が[L,R]である組み合わせ数を答える

解説

セグメントツリーで解く。
　
セグメントツリーの各要素に以下の情報を与えておく。

• cnt 区間内の要素数
• ans 区間内の部分集合で最大値が[L,R]である数
• min_left 左側でL未満の数が何個続いているか
• min_right 右側でL未満の数が何個続いているか
• max_left 左側にR以下の数が何個続いているか
• max_right 右側にR以下の数が何個続いているか

　
このとき、隣接する要素左のx,右のyをマージするときは、

• cnt = x.cnt + y.cnt
• ans = x.ans + y.ans + x.max_right * y.max_left - x.min_right * y.min_left
  • 追加でカウントするべき区間は左側の要素から右側の要素に渡る区間である
  • 最大値としてRより大きい数が含まれてはいけないから、R以下の数だけの区間を足す x.max_right * y.max_left
  • 最大値としてLより小さくてはダメなので、Lより小さい数だけの区間をそこから引く x.min_right * y.min_left
• min_left = x.min_left (+y.min_left)
  • もし、xが全てLより小さいならば、yの小さい方も含む
  • 以下、同様に更新していく
• min_right = y.min_right (+x.min_right)
• max_left = x.max_left (+y.max_left)
• max_right = y.max_right (+x.max_right)

　
あとは、乗せて取ってきて答えるだけ。

typedef long long ll;
int N, Q, L, R;
//---------------------------------------------------------------------------------------------------
struct func {
    ll cnt, ans, min_left, min_right, max_left, max_right;
    func() { cnt = 0; }
    func(int x) {
        cnt = 1;
        if (L <= x and x <= R) ans = 1;
        else ans = 0;
 
        if (x < L) min_left = min_right = 1;
        else min_left = min_right = 0;
 
        if (R < x) max_left = max_right = 0;
        else max_left = max_right = 1;
    }
};
func operator*(func& x, func& y) {
    if (x.cnt == 0) return y;
    if (y.cnt == 0) return x;
 
    func z;
 
    z.cnt = x.cnt + y.cnt;
    ll d = x.max_right * y.max_left - x.min_right * y.min_left;
    assert(0 <= d);
    z.ans = x.ans + y.ans + d;
    
    z.min_left = x.min_left;
    if (x.min_left == x.cnt) z.min_left += y.min_left;
 
    z.min_right = y.min_right;
    if (y.min_right == y.cnt) z.min_right += x.min_right;
 
    z.max_left = x.max_left;
    if (x.max_left == x.cnt) z.max_left += y.max_left;
 
    z.max_right = y.max_right;
    if (y.max_right == y.cnt) z.max_right += x.max_right;
 
    return z;
}
SegTree<func, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q >> L >> R;
    rep(i, 0, N) st.update(i, func(0));
    rep(i, 0, Q) {
        int t, x, y; cin >> t >> x >> y;
        if (t == 1) st.update(x - 1, func(y));
        else {
            auto f = st.get(x - 1, y);
            if (f.cnt == 0) printf("0\n");
            else printf("%lld\n", f.ans);
        }
    }
}