【题解】Luogu P4344 [SHOI2015]脑洞治疗仪

原题传送门：P4344 [SHOI2015]脑洞治疗仪

前置芝士：珂朵莉树

窝博客里对珂朵莉树的介绍

没什么好说的自己看看吧

珂朵莉树好题啊

我一开始一直Re65

后来重构代码就ac了，或许是rp问题

线段树做法好像很慢啊

我的珂朵莉树吸氧后目测luogu最优解第二，不知最优解匿名大佬怎么写的

操作1：把区间推平成0，开脑洞？？？珂朵莉树基本操作

操作2：把区间中的1的数量统计一下并变成0，暴力去被修补脑洞的区间填补（细节看代码来理解）

操作3：查询区间中最长连续的1，暴力扫一遍就行

#pragma GCC optimize("O3")

#include<bits/stdc++.h>

#define IT set<node>::iterator

using namespace std;

struct IO_Tp

{

    static const int _I_Buffer_Size = 1 << 24;

    char _I_Buffer[_I_Buffer_Size];

    char* _I_pos;

    static const int _O_Buffer_Size = 1 << 24;

    char _O_Buffer[_O_Buffer_Size];

    char* _O_pos;

    IO_Tp() : _I_pos(_I_Buffer), _O_pos(_O_Buffer)

    {

        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);

    }

    ~IO_Tp()

    {

        fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);

    }

    inline bool is_digit(const char ch)

    {

        return '0' <= ch && ch <= '9';

    }

    inline IO_Tp& operator>>(int& res)

    {

        res = 0;

        while (!is_digit(*_I_pos))

            ++_I_pos;

        do

            (res *= 10) += (*_I_pos++) & 15;

        while (is_digit(*_I_pos));

        return *this;

    }

    inline IO_Tp& operator<<(int n)

    {

        static char _buf[10];

        char* _pos(_buf);

        do

            *_pos++ = '0' + n % 10;

        while (n /= 10);

        while (_pos != _buf)

            *_O_pos++ = *--_pos;

        return *this;

    }

    inline IO_Tp& operator<<(char ch)

    {

        *_O_pos++ = ch;

        return *this;

    }

} IO;

inline int Max(register int a,register int b)

{

    return a>b?a:b;

}

struct node

{

    int l,r;

    mutable bool v;

    node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}

    bool operator<(const node& o) const

    {

        return l < o.l;

    }

};

set<node> s;

IT split(int pos)

{

    IT it = s.lower_bound(node(pos));

    if (it != s.end() && it->l == pos)

        return it;

    --it;

    int L = it->l, R = it->r;

    bool V = it->v;

    s.erase(it);

    s.insert(node(L, pos-1, V));

    return s.insert(node(pos, R, V)).first;

}

void assign_val(int l,int r,bool v)

{

    IT itr = split(r+1),itl = split(l);

    s.erase(itl, itr);

    s.insert(node(l, r, v));

}

void scure(int l,int r,int a,int b)

{

    IT itr = split(r+1),itl = split(l),it = itl;

    int sum=0;

    for(; itl != itr; ++itl)

        if(itl->v)

            sum+=itl->r-itl->l+1;

    s.erase(it,itr);

    s.insert(node(l,r,0));

    if(!sum)

        return;

    itr = split(b+1),itl = split(a),it = itl;

    if(sum>=b-a+1)

    {

    	s.erase(itl,itr);

    	s.insert(node(a,b,1));

    	return;

    }

    for( ; itl != itr; ++itl)

        if(!itl->v)

        {

            sum-=itl->r-itl->l+1;

            if(sum<0)

            {

                assign_val(itl->l,itl->r+sum,1);

                break;

            }

            else

                itl->v=1;

        }

}

void sMax(int l,int r)

{

    IT itr = split(r+1),itl = split(l);

    int maxn=0,now=0;

    for(; itl != itr; ++itl)

        if(!itl->v)

            now+=itl->r-itl->l+1;

        else if(now)

            maxn=Max(maxn,now),now=0;

    IO<<Max(maxn,now)<<'\n';

}

int main()

{

    int n,m;

    IO>>n>>m;

    s.insert(node(1,n,1));

    while(m--)

    {

        int op,l,r;

        IO>>op>>l>>r;

        if(op==0)

            assign_val(l,r,0);

        else if(op==1)

        {

            int a,b;

            IO>>a>>b;

            scure(l,r,a,b);

        }

        else

            sMax(l,r);

    }

    return 0;

}