题解：CF1146E Hot is Cold

· · 题解

这个题直接做就是好做的，注意到平衡树区间取反有交合并的势能是对的，把所有数放到平衡树上，每次把对应区间分裂出来，打上标记，然后合并回去就好了。

每个节点维护子树最大值和最小值，取反的时候记得要交换这两个值并翻转整个区间以保证序列是有序的。

放一个 WBLT 值域有交合并的伪代码：

// WBLT 值域有交启发式合并
ptr hmerge(ptr x,ptr y)
{
    if(!x)return y;
    if(!y)return x;
    if(x->max<=y->min)return merge(x,y);
    // ptr merge(ptr,ptr) 表示直接合并两颗树并维护平衡，返回根
    if(y->max<=x->min)return merge(y,x);
    if(x->size<y->size)swap(x,y);
    if(y->size==1)
    {
        auto[a,b]=split_v(x,y->max);
        // pair<ptr,ptr> split_v(ptr,val) 表示按值分裂，返回左右子树的根
        x=merge(merge(a,y),b);
        return x;
    }
    push_down(x);
    ptr c=x->ls,d=x->rs;
    delete x;
    auto[a,b]=f.split_v(y,c->max);
    return merge(hmerge(c,a),hmerge(d,b));
}

"Merging treaps" -- or how to merge sorted sets in good complexity... - Codeforces

P5494 题解 & 平衡树合并 - 洛谷专栏

关于 WBLT 的有交合并 - 洛谷