LibreOJ 2037 「SHOI2015」脑洞治疗仪

修补操作比较麻烦，其他都是珂朵莉树的基本操作。

首先统计原材料区间有多少个 1，并把它们摊平成 0。
然后在待修补区间的迭代器上迭代，并让可使用的 1 的个数逐渐减少，直到无法填平整个结点的区间。
把它切开然后摊平。

具体细节见代码，参考了 yzhang 大佬的写法。

代码：

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int N = 2e5;
int n,m;
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;
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 continuity(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    int ret = 0,cur = 0;
    for(;itl != itr;++itl)
        if(!itl->val)
            cur += itl->r - itl->l + 1;
        else
        {
            ret = max(ret,cur);
            cur = 0;
        }
    return max(ret,cur);
}
inline void cure(int tl,int tr,int l,int r)
{
    IT itr = split(tr + 1),itl = split(tl);
    int sum = 0;
    for(;itl != itr;++itl)
        sum += itl->val * (itl->r - itl->l + 1);
    assign(tl,tr,0);
    if(!sum)
        return ;
    itr = split(r + 1),itl = split(l);
    if(sum >= r - l + 1)
    {
        tree.erase(itl,itr);
        tree.insert((node){l,r,1});
        return ;
    }
    for(;itl != itr;++itl)
        if(!itl->val)
        {
            sum -= itl->r - itl->l + 1;
            if(sum <= 0)
            {
                assign(itl->l,itl->r + sum,1);
                break;
            }
            else
                itl->val = 1;
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    tree.insert((node){1,n,1});
    int op,a,b,c,d;
    while(m--)
    {
        scanf("%d%d%d",&op,&a,&b);
        if(op == 0)
            assign(a,b,0);
        else if(op == 1)
            scanf("%d%d",&c,&d),cure(a,b,c,d);
        else
            printf("%d\n",continuity(a,b));
    }
}