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

题目大意

初始你有两个长度为的序列。

序列满足下面的要求：。接下来你有三种操作：

1. 把赋值成。
2. 把这一段区间全部按位取反，即互换。
3. 求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你需要回答这样的操作答案是多少？

操作最多有个。

Solution

考点：线段树区间合并

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

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

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

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

那么对应的我们就要在中维护这个变量，在中往下推标记。

我们设计一个函数他会帮我们求出在区间中上一次最大值是并且结尾是的答案贡献。

那么我们在线段树从下往上更新的时候，我们可以知道一定会先等于左子数的最大值，接下来拿着左子数的最大值去查询，就可以用右子树全部可能的点依次更新的最值和结尾的，并且的返回值就是区间里面它的不下降子序列长度。

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

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

然后求解答案的过程就去线段树区间上找到查询给的区间累加求合即可，时间复杂度。

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