LibreOJ 2055 「TJOI / HEOI2016」排序

这题在线做法貌似很麻烦呢……

后来看题解发现了一种奇怪的做法：二分答案 + 线段树。
但是这里线段树可以用珂朵莉树替换，于是我写了珂朵莉树。

二分结果的值为 mid，然后把整个序列每个 ai，若 ai≤mid，使 ai←1，否则使 ai=0。
那么 0/1 序列的升序和降序用线段树就可以 logn 搞，计算区间内 1 的个数然后乱搞一下就好，
需要用到线段树区间覆盖，区间求和。
但是这一点我用了珂朵莉树。

判定的时候跑一遍所有的修改操作，最后检查 aq 是否还是 1。

代码：

#include <cstdio>
#include <set>
using namespace std;
const int N = 1e5;
const int M = 1e5;
int n,m,q;
int a[N + 10];
int l,r,mid,ans;
struct node
{
    int l,r;
    mutable int val;
    inline bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
set<node> tree;
typedef set<node>::iterator IT;
inline IT split(int x)
{
    IT it = tree.lower_bound((node){x,0,0});
    if(it != tree.end() && it->l == x)
        return it;
    --it;
    int l = it->l,r = it->r;
    int v = it->val;
    tree.erase(it);
    tree.insert((node){l,x - 1,v});
    return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,int val)
{
    IT itr = split(r + 1),itl = split(l);
    tree.erase(itl,itr);
    tree.insert((node){l,r,val});
}
inline int query(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    int ret = 0;
    for(;itl != itr;++itl)
        ret += itl->val * (itl->r - itl->l + 1);
    return ret;
}
struct s_change
{
    int l,r,op;
} chg[M + 10];
bool check()
{
    tree.clear();
    int last = a[1] >= mid,cnt = 1;
    for(register int i = 2;i <= n;++i)
        if((a[i] >= mid) == last)
            ++cnt;
        else
        {
            tree.insert((node){i - cnt,i - 1,last});
            last = a[i] >= mid;
            cnt = 1;
        }
    tree.insert((node){n - cnt + 1,n,last});
    for(register int i = 1;i <= m;++i)
    {
        int sum = query(chg[i].l,chg[i].r);
        if(sum == chg[i].r - chg[i].l + 1)
            assign(chg[i].l,chg[i].r,1);
        else if(!chg[i].op)
            assign(chg[i].l,chg[i].r - sum,0),assign(chg[i].r - sum + 1,chg[i].r,1);
        else
            assign(chg[i].l,chg[i].l + sum - 1,1),assign(chg[i].l + sum,chg[i].r,0);
    }
    return split(q)->val;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d",&chg[i].op,&chg[i].l,&chg[i].r);
    scanf("%d",&q);
    l = 1,r = n;
    while(l <= r)
    {
        mid = l + r >> 1;
        if(check())
            ans = mid,l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d\n",ans);
}