2021牛客暑期多校训练营7 B、xay loves monotonicity

题目大意

初始你有两个长度为 $n(1\le n\le 2·10^5)$ 的序列 $a_i,b_i$ 。

序列满足下面的要求： $1\le a_i\le 10^9,b_i\in\{0,1\}$ 。接下来你有三种操作：

把 $a_i$ 赋值成 $x$ 。
把 $[b_l,b_r]$ 这一段区间全部按位取反，即 $01$ 互换。
求在 $[l,r]$ 这个区间中必选 $a_l$ 构成的最长不下降子序列，假设为 $a_1,a_3,a_4$ ，那么我们取出 $b_1,b_3,b_4$ 构成一个 $01$ 串，这个串中有多少个 $01$ 交接处就是这个区间 $[l,r]$ 的答案，你需要回答这样的操作答案是多少？

操作最多有 $2·10^5$ 个。

Solution

考点：线段树区间合并

如果有写过用线段树维护最大连续子段和的读者可能会更好的理解这篇题解。

我们先看操作 $1、2$ 都是线段树的基础操作了，单点更新区间修改，打上 $lazy$ 标记即可，我们重点关注操作 $3$ 。

我们如何快速的找到区间的最长不下降子序列呢？

首先我们把区间映射到线段树的区间上去看，对于线段树节点维护的区间 $[l,r]$ 来说，我们另外定义一下变量 $maxi$ 代表区间最大值， $bit$ 代表这个区间的最长不下降子序列结尾的下标对应的 $b_i$ ， $len$ 代表这个区间的最长不下降子序列长度。

那么对应的我们就要在 $push\_up$ 中维护这 $3$ 个变量，在 $push\_down$ 中往下推 $lazy$ 标记。

我们设计一个函数 $query(rt,l,r,pre\_maxi,pre\_bit)$ 他会帮我们求出在区间 $[l,r]$ 中上一次最大值是 $pre\_maxi$ 并且结尾是 $pre\_bit$ 的答案贡献。

那么我们在线段树从下往上更新的时候，我们可以知道 $maxi[rt]$ 一定会先等于左子数的最大值，接下来拿着左子数的最大值去查询 $\\query(rt<<1|1,\frac{l+r}{2}+1,r,maxi[rt],bit[rt])$ ，就可以用右子树全部可能的点依次更新 $rt$ 的最值和结尾的 $b_i$ ，并且 $query()$ 的返回值就是区间里面它的不下降子序列长度。

但是在 $query()$ 的时候也会遇到区间，如果这个区间的左子树的最大值小于了之前结尾的最大值说明这个左子树对于不下降子序列来说没有一点贡献，直接去找右子树，否则就要先递归一下左子树求出左边的长度，然后更新了之前的最大值再去递归右子树。

但是我们会发现这样复杂度有点高了，我们要仔细的思考我们处理过那些区间信息，哪些信息是待处理的。由于我们的区间是从底向上合并，所以对于任意一棵树来说他的子树一定在之前就是处理完成的，那么我们 $query()$ 查询的本质是 $rt$ 的右子树有没有谁的最值大于 $rt$ 的左子树，那么对于他右子树这些区间，之前一定是经历过 $push\_up$ 了的，所以这些区间的 $len[rt]$ 都是已经算出来的答案了，所以对于区间 $rt$ 的子区间来说，它右子树带来的不下降子序列长度就没需要去重新 $query()$ 了，因为你之前已经维护出了 $len[rt]$ 和 $len[ls]$ ，那么根据我们在 $push\_up$ 里面写的 $len[rt]=len[ls]+query(rs)$ ，我们等价的知道 $query(rs) = len[rt] - len[ls]$ ，这也就在外面找完左边的长度之后重新 $query(rs)$ 的步骤给省去了。

然后求解答案的过程就去线段树区间上找到查询给的区间累加求合即可，时间复杂度 $O(n\log^2n)$ 。

const int N = 2e5 + 7;
int a[N], b[N];

struct SegTree {
#define mid (l+r>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r

    int maxi[N << 2], len[N << 2];
    int bit[N << 2], lazy[N << 2];

    void push_down(int rt) {
        if (lazy[rt] == 0)    return;
        bit[ls] ^= 1, lazy[ls] ^= 1;
        bit[rs] ^= 1, lazy[rs] ^= 1;
        lazy[rt] = 0;
    }

    int query(int rt, int l, int r, int& pre_max, int& pre_bit) {
        if (l == r) {
            if (maxi[rt] >= pre_max) { // 右子树更新之前父亲的值
                int res = pre_bit != bit[rt];
                if (pre_max == -1)    res = 0; // 说明是第一个点 0/1 都不计算
                pre_max = maxi[rt];
                pre_bit = bit[rt];
                return res;
            }
            return 0;
        }
        push_down(rt);
        if (maxi[ls] >= pre_max) {
            int res = query(lson, pre_max, pre_bit) + len[rt] - len[ls];
            //debug(res);
            pre_max = maxi[rt];
            pre_bit = bit[rt];
            return res;
        }
        else
            return query(rson, pre_max, pre_bit);
    }

    void push_up(int rt, int l, int r) {
        maxi[rt] = maxi[ls];
        bit[rt] = bit[ls];
        len[rt] = len[ls] + query(rson, maxi[rt], bit[rt]); // 用已经计算的ls，再去查询rs可选的更新rt
    }

    void build(int rt, int l, int r) {
        if (l == r) {
            maxi[rt] = a[l];
            bit[rt] = b[l];
            len[rt] = 1;
            lazy[rt] = 0;
            return;
        }
        build(lson);
        build(rson);
        push_up(rt, l, r);
    }

    void update(int rt, int l, int r, int pos, int v) {
        if (l == r) {
            maxi[rt] = v;
            return;
        }
        push_down(rt);
        if (pos <= mid)    update(lson, pos, v);
        else update(rson, pos, v);
        push_up(rt, l, r);
    }

    void update2(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            bit[rt] ^= 1;
            lazy[rt] ^= 1;
            return;
        }
        push_down(rt);
        if (R <= mid)    update2(lson, L, R);
        else if (L > mid)    update2(rson, L, R);
        else {
            update2(lson, L, mid);
            update2(rson, mid + 1, R);
        }
        push_up(rt, l, r);
    }

    int get_ans(int rt, int l, int r, int L, int R, int& pre_max, int& pre_bit) {
        if (L <= l && r <= R)    return query(rt, l, r, pre_max, pre_bit);
        push_down(rt);
        if (R <= mid)    return get_ans(lson, L, R, pre_max, pre_bit);
        if (L > mid)    return get_ans(rson, L, R, pre_max, pre_bit);
        return get_ans(lson, L, mid, pre_max, pre_bit) + get_ans(rson, mid + 1, R, pre_max, pre_bit);
    }

}A;



int solve() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = read();
    }
    A.build(1, 1, n);
    int Q = read();
    while (Q--) {
        int op = read(), t1 = read(), t2 = read();
        if (op == 1) {
            A.update(1, 1, n, t1, t2);
        }
        else if (op == 2) {
            A.update2(1, 1, n, t1, t2);
        }
        else {
            int pre_max = -1, pre_bit = 0;
            print(A.get_ans(1, 1, n, t1, t2, pre_max, pre_bit));
        }
    }

    return 1;
}