线段树……好……难……

看到本题数据范围，想到两种做法：

1. 分块，时间复杂度 $O(n\sqrt n)$。
2. 线段树，时间复杂度 $O(n\log n)$。

温馨提示：时间复杂度 $O(n\sqrt n)$ 的珂朵莉树被卡了

为什么可以线段树？因为最大子段和支持结合律。

关于最大子段和。

如果要 $O(\log n)$ 询问最大子段和，只有两种办法：

1. 矩阵乘法（这题不可用，因为有区间取反）
2. 线段树

其实都是一样的思路，维护三个 tag，分别为最大前缀和、最大后缀和、最大子段和。没思路的可以去看看 SPOJ GSS 系列。

转移方程即为：

$$\begin{matrix} pre_i=max\{pre_{ls},sum_{ls}+pre_{rs}\}\\ suf_i=max\{suf_{rs},sum_{rs}+suf_{ls}\}\\ ans_i=max\{ans_{ls},ans_{rs},suf_{ls}+pre_{rs}\} \end{matrix} $$

关于区间取反。

有两种含义：

1. 对区间里的每一个数取反，即 $\forall i\in\lbrack l,r\rbrack,a_i\leftarrow!a_i$。
2. 整个区间反转。

如果配合上最大子段和，会发现：第一个问题会让我们多维护三个 tag，因为零变一、一变零需要对三个 tag 一一交换；而第二个问题需要配合上文艺平衡树使用。

本题的问题即第一种含义。

所以代码就出来了：

我写的是动态开点线段树，使得它非常难调，随随便便就 $\color{#9D3DCF}\tt RE$ 了。

11月11日。后来我去做了一下这些题（这些题也是练习）：

1. [TJOI2009]开关（这题我甚至录了音）
2. [USACO08NOV]Light Switching G
3. XOR的艺术

然后我明白了：pushdown 的过程中如果没有左右节点，就需要 new 一个节点，否则就会 $\color{#9D3DCF}\tt RE$。假的，经测试，不用 new 节点也可以，因为如果是叶节点肯定会返回，而不用 pushdown

11月12日。我开始肝这题。由于之前我已经写好了线段树的代码，我找到了几个 bug 并将其改正，在一番调试后，我 $\color{#52C41A}AC$ 了本题。

本题的操作优先级为：先赋值、再取反。

几种不通过的原因。

1. $\color{#E74C3C}0$：有几种原因。首先，检查有没有死循环等等。其次，在查询最大子段和时需要 将整个 tag 打包传回，以便合并。
2. $\color{#E74C3C}20$：检查在对节点进行取反操作时有没有将 区间赋的值 改变。
3. $\color{#F39D11}30$：检查你是否写了时间复杂度错误的算法或数据结构，如 $O(n\log n)$ 查询区间最大子段和。
4. 非 $\color{#52C41A}100$ 分：检查有没有把变量名打错，或者在构造结构体时变量的位置对应错，等等。
5. $\color{#52C41A}100$ 分但没有 $\color{#52C41A}AC$：检查有没有使用错误时间复杂度的算法或数据结构，如时间复杂度错误的颜色段均摊。

然后你就可以愉快地 $\color{#52C41A}AC$ 了！

练习：

1. [TJOI2009]开关
2. [USACO08NOV]Light Switching G
3. XOR的艺术
4. GSS1 - Can you answer these queries I
5. GSS3 - Can you answer these queries III

如果你已经完全掌握至少一种不基于旋转的平衡树，还可以尝试如下题目：

1. GSS6 - Can you answer these queries VI

如果你已经完全掌握计算几何，还可以尝试如下题目：（提示：一样的做法，只不过维护的东西变成了 凸包，合并时用 闵可夫斯基和）

1. [Ynoi2015]世界上最幸福的女孩（使用朴素做法可以到 $O((n+m)\log^2 n)$）
2. [Ynoi2018]末日时在干什么？有没有空？可以来拯救吗？（使用朴素做法可以到 $O((n+m)\sqrt n\log n)$）

部分代码：（为增加可读性，使用了注释）

class Data {
public:
    int l = 0, r = 0;
    int zero_pre = 0, zero_suf = 0, zero_ans = 0, one_pre = 0, one_suf = 0, one_ans = 0;
    int sum = 0;
    int cover = -1;
    bool is_reversed = false;
    typedef bool value_type;
    // default constructor
    Data(int, int, int, int, int, int, int, int, int, int, bool) = default;
    // copy constructor
    Data &operator=(const Data &) = default;
    // destructor
    ~Data() = default;
    Data(const Data &) = default;
#if __cplusplus >= 201103L
    Data(Data &&) = default; // move constructor
    Data &operator=(Data &&) = default; // move assignment operator
#endif
    inline int size() const { return r - l + 1; } // size of this value
    inline void update(bool iv) { // fill [l,r] with iv
        // ...
        if (iv) {
            zero_pre = zero_suf = zero_ans = 0;
            one_pre = one_suf = one_ans = size();
        }
        else {
            zero_pre = zero_suf = zero_ans = size();
            one_pre = one_suf = one_ans = 0;
        }
    }
    /****************************
     * 
     * @brief  merge d1 and d2 to the result. This is a help function of @code SegTree::pushup.
     * 
     * @param d1  the first data to merge.
     * @param d2  the second data to merge.
     *
     * @return  the result of merging.
     * 
     ****************************/
    friend Data merge(const Data& d1, const Data& d2);
    // flip [l,r]
    void reverse() {
        // ...
        if (cover != -1) cover = !cover;
    }
    /*********************
     * 
     * @brief  split value to new1 and new2. This is a help function of @code SegTree::pushdown().
     * 
     * @param new1  the first data to split.
     * @param new2  the second data to split.
     * 
     * @return  none
     * 
     *********************/
    void split(Data &new1, Data &new2) {
        if (cover != -1) {
            is_reversed = false;
            // ...
            if (cover) {
                new1.zero_pre = new1.zero_suf = new1.zero_ans = 0;
                new1.one_pre = new1.one_suf = new1.one_ans = new1.size();
                new2.zero_pre = new2.zero_suf = new2.zero_ans = 0;
                new2.one_pre = new2.one_suf = new2.one_ans = new2.size();
            }
            else {
                new1.zero_pre = new1.zero_suf = new1.zero_ans = new1.size();
                new1.one_pre = new1.one_suf = new1.one_ans = 0;
                new2.zero_pre = new2.zero_suf = new2.zero_ans = new2.size();
                new2.one_pre = new2.one_suf = new2.one_ans = 0;
            }
            cover = -1;
        }
        if (is_reversed) {
            // ...
            if (new1.cover != -1) new1.cover = !new1.cover;
            else new1.is_reversed = !new1.is_reversed;
            if (new2.cover != -1) new2.cover = !new2.cover;
            else new2.is_reversed = !new2.is_reversed;
            // swaps
            is_reversed = false;
        }
    }
};
template <typename _Tp>
class SegTree { // segment tree
public:
    _Tp value;
    SegTree *left, *right;
    // push up tags
    void pushup() { value = merge(left->value, right->value); }
    // push down tags
    void pushdown() { value.split(left->value, right->value); }
public:
    // fill [l,r] with v
    void update(int, int, bool);
    // flip [l,r]
    void reverse(int, int);
    // query the sum of [l,r]
    int query_sum(int, int);
    // query the maxinum sum of subsequences of [l,r]
    _Tp query_ans(int, int);
    // build the segment tree
    void build(const int*, int, int);
    // default constructor
    SegTree(const _Tp&, SegTree<_Tp>*, SegTree<_Tp>*) = default;
    // destructor
    ~SegTree() = default;
};