LOJ#6777. 「2021 营员交流」大毒瘤

Yuzu_Soft · 2024-07-15 11:01:59 · 题解

维护相同颜色段好题

其实是和P5066一样恶心的玩意

大常数垃圾实现

被分块暴踩

考虑对于极大的火，相同颜色的树的段都缩成一个平衡树上的点

然后我们看看每个操作：

1. 区间加 剖出需要的段，打标记
2. 区间和 维护区间和，剖出需要的段
3. 放火 剖出那个点，进行修改
4. 灭火 维护每个子树有没有火，暴力删除
5. 火焰蔓延 打标记，会影响区间和等信息，扩展火焰段，收缩与火焰相邻的段，还会产生长度为 0，-1 的段

具体而言，我们使用一颗无旋treap 进行维护。对于每个点，首先需要区间树高的 col（火为 -1），代表的区间 [l,r]，子树和的 sum，加法标记 addtag 与火焰标记 firetag。

区间加操作时，为了求出新的 sum，我们维护区间不是火的格子数量 cntt。

然后对于火焰，我们考虑记录每个段左/右是否为火的 lf/rf 以及两者的和 f，为了处理烧没的段我们分别求出 f=1 以及 f=2 的段长度最小值 mif1len和mif2len。火焰蔓延会影响子树和 sum 和子树树的格子数 cntt，因此要维护子树 f 之和 sumf 与子树 f*col 之和的 sumfcol。

扑灭火焰时维护区间 col 最小值（也可以直接维护存不存在 -1），由于火焰段数为 \mathcal{O}(q) 的于是暴力删，空段也同理直接删

于是这个 \log 做法（？）做完了，但是某些实现很差所以很慢。

#include<bits/stdc++.h>//I love Kagamine Rin forever!
#define ll long long
using namespace std;//() is so cute!

int n,q;

int getrnd(){return rand();}

struct node
{
    int siz,rnd,l,r;
    int ls,rs;
    ll col;//height  -1: fire
    int cntt;//cnttree
    int lf,rf,f;//fire: 0 wood: cnt of fire beside
    ll sum;//sum of col*(r-l+1)[col!=-1]
    int sumf;//sum of f
    ll sumfcol;//sum of f*col[col!=-1]
    ll addtag;
    int firetag;
    ll micol;
    int mif1len,mif2len;

    void init(ll _col,int _l,int _r,int _lf,int _rf)
    {
        siz=1;
        rnd=getrnd();
        ls=rs=0;
        l=_l,r=_r;
        col=micol=_col;
        lf=_lf;
        rf=_rf;
        sumf=f=lf+rf;
        cntt=_col==-1?0:r-l+1;
        sum=_col==-1?0:col*(r-l+1);
        sumfcol=_col==-1?0:col*f;
        addtag=0;
        firetag=0;
        mif1len=mif2len=1e9;
        if(f==1)mif1len=r-l+1;
        if(f==2)mif2len=r-l+1;
    }

    void pushadd(ll _addtag)
    {
        if(col!=-1)col+=_addtag;
        if(micol!=-1)micol+=_addtag;
        sum+=_addtag*cntt;
        sumfcol+=_addtag*sumf;
        addtag+=_addtag;
    }

    void pushfire(int _firetag)
    {
        if(col==-1)
        {
            l=max(l-_firetag,1);
            r=min(r+_firetag,n);
        }
        if(lf)l+=_firetag;
        if(rf)r-=_firetag;
        sum-=sumfcol*_firetag;
        cntt-=sumf*_firetag;
        firetag+=_firetag;
        mif1len-=_firetag;
        mif2len-=2*_firetag;
    }
}tr[4000005];

int sz,rt;

void pushdown(int x)
{
    if(tr[x].addtag)
    {
        if(tr[x].ls)tr[tr[x].ls].pushadd(tr[x].addtag);
        if(tr[x].rs)tr[tr[x].rs].pushadd(tr[x].addtag);
        tr[x].addtag=0;
    }
    if(tr[x].firetag)
    {
        if(tr[x].ls)tr[tr[x].ls].pushfire(tr[x].firetag);
        if(tr[x].rs)tr[tr[x].rs].pushfire(tr[x].firetag);
        tr[x].firetag=0;
    }
}

void maintain(int x)
{
    tr[x].cntt=(tr[x].col==-1?0:tr[x].r-tr[x].l+1)+tr[tr[x].ls].cntt+tr[tr[x].rs].cntt;
    tr[x].siz=1+tr[tr[x].ls].siz+tr[tr[x].rs].siz;
    tr[x].micol=min(tr[x].col,min(tr[tr[x].ls].micol,tr[tr[x].rs].micol));
    tr[x].sumf=tr[x].f+tr[tr[x].ls].sumf+tr[tr[x].rs].sumf;
    tr[x].sum=(tr[x].col==-1?0:tr[x].col)*(tr[x].r-tr[x].l+1)+tr[tr[x].ls].sum+tr[tr[x].rs].sum;
    tr[x].sumfcol=(tr[x].col==-1?0:tr[x].col)*tr[x].f+tr[tr[x].ls].sumfcol+tr[tr[x].rs].sumfcol;
    tr[x].mif1len=min(tr[tr[x].ls].mif1len,tr[tr[x].rs].mif1len);
    tr[x].mif2len=min(tr[tr[x].ls].mif2len,tr[tr[x].rs].mif2len);
    if(tr[x].f==1)tr[x].mif1len=min(tr[x].mif1len,tr[x].r-tr[x].l+1);
    if(tr[x].f==2)tr[x].mif2len=min(tr[x].mif2len,tr[x].r-tr[x].l+1);
}

inline int alloc(ll col,int l,int r,int lf,int rf)
{
    sz++;
    tr[sz].init(col,l,r,lf,rf);
    return sz;
}

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(tr[x].rnd<tr[y].rnd)
    {
        pushdown(x);
        tr[x].rs=merge(tr[x].rs,y);
        maintain(x);
        return x;
    }
    else
    {
        pushdown(y);
        tr[y].ls=merge(x,tr[y].ls);
        maintain(y);
        return y;
    }
}
void split(int u,int siz,int &x,int &y)
{
    if(!u)
    {
        x=y=0;
        return;
    }
    pushdown(u);
    if(tr[tr[u].ls].siz<siz)x=u,split(tr[u].rs,siz-tr[tr[u].ls].siz-1,tr[u].rs,y);
    else y=u,split(tr[u].ls,siz,x,tr[y].ls);
    maintain(u);
}

void splitByL(int u,int val,int &x,int &y)
{
    if(!u)
    {
        x=y=0;
        return;
    }
    pushdown(u);
    if(tr[u].l<val)x=u,splitByL(tr[x].rs,val,tr[x].rs,y);
    else y=u,splitByL(tr[y].ls,val,x,tr[y].ls);
    maintain(u);
}

void splitByR(int u,int val,int &x,int &y)
{
    if(!u)
    {
        x=y=0;
        return;
    }
    pushdown(u);
    if(tr[u].r<=val)x=u,splitByR(tr[x].rs,val,tr[x].rs,y);
    else y=u,splitByR(tr[y].ls,val,x,tr[y].ls);
    maintain(u);
}

int findG(int p)
{
    if(tr[p].l>tr[p].r)
    {
        return tr[tr[p].ls].siz+1;
    }
    pushdown(p);
    if(tr[p].ls&&min(tr[tr[p].ls].mif1len,tr[tr[p].ls].mif2len)<=0)return findG(tr[p].ls);
    if(tr[p].rs&&min(tr[tr[p].rs].mif1len,tr[tr[p].rs].mif2len)<=0)return tr[tr[p].ls].siz+1+findG(tr[p].rs);
    return 0;
}

void delG(int &rt)
{
    int x,y,z,k,lx,fz,a,b;
    int i=0;
    while(k=findG(rt))
    {
        i++;
        split(rt,k-1,x,y);
        split(y,1,y,z);
        if(x&&z)
        {
            split(x,tr[x].siz-1,x,a);
            split(z,1,b,z);
            if(tr[a].col==tr[b].col)
            {
                tr[y].init(tr[a].col,tr[a].l,tr[b].r,tr[a].lf,tr[b].rf);
                z=merge(y,z);
            }
            else
            {
                if(tr[a].col==-1&&tr[b].col!=-1)
                {
                    tr[b].f-=tr[b].lf;
                    tr[b].lf=1;
                    tr[b].f+=tr[b].lf;
                    maintain(b);
                }
                if(tr[a].col!=-1&&tr[b].col==-1)
                {
                    tr[a].f-=tr[a].rf;
                    tr[a].rf=1;
                    tr[a].f+=tr[a].rf;
                    maintain(a);
                }
                x=merge(x,a);
                z=merge(b,z);
            }
        }
        rt=merge(x,z);
    }
}

int findF(int p)
{
    if(tr[p].col==-1)return tr[tr[p].ls].siz+1;
    pushdown(p);
    if(tr[p].ls&&tr[tr[p].ls].micol<0)return findF(tr[p].ls);
    if(tr[p].rs&&tr[tr[p].rs].micol<0)return tr[tr[p].ls].siz+1+findF(tr[p].rs);
    return 0;
} 

void delF(int &rt)
{
    int x,y,z,k,lf,rf,a,b;
    while(k=findF(rt))
    {
        split(rt,k-1,x,y);
        split(y,1,y,z);
        int u=tr[y].l,v=tr[y].r;

        if(x)
        {
            split(x,tr[x].siz-1,x,a);
            tr[a].f-=tr[a].rf;
            tr[a].rf=0;
            maintain(a);
            if(tr[a].col==0)u=tr[a].l;
            else x=merge(x,a);
        }
        if(z)
        {
            split(z,1,b,z);
            tr[b].f-=tr[b].lf;
            tr[b].lf=0;
            maintain(b);
            if(tr[b].col==0)v=tr[b].r;
            else z=merge(b,z);
        }
        lf=rf=0;
        if(x)
        {
            split(x,tr[x].siz-1,x,a);
            if(tr[a].col==-1)lf=1;
            x=merge(x,a);
        }
        if(z)
        {
            split(z,1,b,z);
            if(tr[b].col==-1)rf=1;
            z=merge(b,z);
        }
        x=merge(x,alloc(0,u,v,lf,rf));
        rt=merge(x,z);
    }
}

int a[100005];

int main()
{
    tr[0]=node{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(ll)1e18,(int)1e9,(int)1e9};
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int las=1,i=1;i<=n;i++)
    {
        if(i==n||a[i]!=a[i+1])
        {
            rt=merge(rt,alloc(a[i],las,i,0,0));
            las=i+1;
        }
    }
    for(int op,l,r,v,i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&l);
        if(op==1)
        {
            int x,y,z,_;
            scanf("%d%d",&r,&v);
            splitByL(rt,l,x,y);
            splitByR(y,r,y,z);
            if(x)
            {
                split(x,tr[x].siz-1,x,_);
                if(tr[_].col!=-1)
                {
                    if(tr[_].r>r)
                    {
                        z=merge(alloc(tr[_].col,r+1,tr[_].r,0,tr[_].rf),z);
                        y=alloc(tr[_].col,l,r,0,0);
                        tr[_].init(tr[_].col,tr[_].l,l-1,tr[_].lf,0);
                    }
                    else if(tr[_].r>=l)
                    {
                        y=merge(alloc(tr[_].col,l,tr[_].r,0,tr[_].rf),y);
                        tr[_].init(tr[_].col,tr[_].l,l-1,tr[_].lf,0);
                    }
                }
                x=merge(x,_);
            }
            if(z)
            {
                split(z,1,_,z);
                if(tr[_].col!=-1&&tr[_].l<=r)
                {
                    y=merge(y,alloc(tr[_].col,tr[_].l,r,tr[_].lf,0));
                    tr[_].init(tr[_].col,r+1,tr[_].r,0,tr[_].rf);
                }
                z=merge(_,z);
            }
            tr[y].pushadd(v);
            rt=merge(x,merge(y,z));
        }
        else if(op==2)
        {
            int x,y,z,_;
            scanf("%d",&r);
            splitByL(rt,l,x,y);
            splitByR(y,r,y,z);
            ll ans=tr[y].sum;
            if(x)
            {
                split(x,tr[x].siz-1,x,_);
                if(tr[_].r>=l)if(tr[_].col!=-1)ans+=tr[_].col*(min(tr[_].r,r)-l+1);
                x=merge(x,_);
            }
            if(z)
            {
                split(z,1,_,z);
                if(tr[_].l<=r)if(tr[_].col!=-1)ans+=tr[_].col*(r-tr[_].l+1);
                z=merge(_,z);
            }
            printf("%lld\n",ans);
            rt=merge(x,merge(y,z));
        }
        else if(op==3)
        {
            v=l;
            int x,y,z,_,a,b;
            splitByL(rt,v+1,y,z);
            split(y,tr[y].siz-1,x,y);
            if(tr[y].col!=-1)
            {
                l=v,r=v;
                if(tr[y].l==tr[y].r)
                {
                    if(x)
                    {
                        split(x,tr[x].siz-1,x,a);
                        if(tr[a].col==-1)l=tr[a].l;
                        else x=merge(x,a);
                    }
                    if(z)
                    {
                        split(z,1,b,z);
                        if(tr[b].col==-1)r=tr[b].r;
                        else z=merge(b,z);
                    }
                    tr[y].init(-1,l,r,0,0);
                    if(x)
                    {
                        split(x,tr[x].siz-1,x,a);
                        tr[a].f-=tr[a].rf;
                        tr[a].rf=1;
                        tr[a].f+=tr[a].rf;
                        maintain(a);
                        x=merge(x,a);
                    }
                    if(z)
                    {
                        split(z,1,b,z);
                        tr[b].f-=tr[b].lf;
                        tr[b].lf=1;
                        tr[b].f+=tr[b].lf;
                        maintain(b);
                        z=merge(b,z);
                    }
                }
                else if(tr[y].l==v)
                {
                    tr[y].init(tr[y].col,v+1,tr[y].r,1,tr[y].rf);
                    if(x)
                    {
                        split(x,tr[x].siz-1,x,a);
                        if(tr[a].col==-1)l=tr[a].l;
                        else x=merge(x,a);
                    }
                    y=merge(alloc(-1,l,r,0,0),y);
                    if(x)
                    {
                        split(x,tr[x].siz-1,x,a);
                        tr[a].f-=tr[a].rf;
                        tr[a].rf=1;
                        tr[a].f+=tr[a].rf;
                        maintain(a);
                        x=merge(x,a);
                    }
                }
                else if(tr[y].r==v)
                {
                    tr[y].init(tr[y].col,tr[y].l,v-1,tr[y].lf,1);
                    if(z)
                    {
                        split(z,1,b,z);
                        if(tr[b].col==-1)r=tr[b].r;
                        else z=merge(b,z);
                    }
                    y=merge(y,alloc(-1,l,r,0,0));
                    if(z)
                    {
                        split(z,1,b,z);
                        tr[b].f-=tr[b].lf;
                        tr[b].lf=1;
                        tr[b].f+=tr[b].lf;
                        maintain(b);
                        z=merge(b,z);
                    }
                }
                else
                {
                    y=merge(alloc(tr[y].col,tr[y].l,v-1,tr[y].lf,1),merge(alloc(-1,v,v,0,0),alloc(tr[y].col,v+1,tr[y].r,1,tr[y].rf)));
                }
            }
            rt=merge(merge(x,y),z);

        }
        else
        {
            int x,y,z,_;
            scanf("%d",&r);
            int a,b;
            splitByL(rt,l,x,y);
            splitByR(y,r,y,z);
            if(x)
            {
                split(x,tr[x].siz-1,x,_);
                if(tr[_].r>r)
                {
                    z=merge(alloc(tr[_].col,r+1,tr[_].r,0,tr[_].rf),z);
                    y=alloc(tr[_].col,l,r,0,0);
                    tr[_].init(tr[_].col,tr[_].l,l-1,tr[_].lf,0);
                }
                else if(tr[_].r>=l)
                {
                    y=merge(alloc(tr[_].col,l,tr[_].r,0,tr[_].rf),y);
                    tr[_].init(tr[_].col,tr[_].l,l-1,tr[_].lf,0);
                }
                x=merge(x,_);
            }
            if(z)
            {
                split(z,1,_,z);
                if(tr[_].l<=r)
                {
                    y=merge(y,alloc(tr[_].col,tr[_].l,r,tr[_].lf,0));
                    tr[_].init(tr[_].col,r+1,tr[_].r,0,tr[_].rf);
                }
                z=merge(_,z);
            }
            delF(y);
            if(x)
            {
                split(x,tr[x].siz-1,x,a);
                split(y,1,_,y);
                if(tr[a].col==-1)
                {
                    tr[_].f-=tr[_].lf;
                    tr[_].lf=1;
                    tr[_].f+=tr[_].lf;
                    maintain(_);
                }
                else if(tr[a].col==tr[_].col)
                {
                    tr[_].init(tr[_].col,tr[a].l,tr[_].r,tr[a].lf,tr[_].rf);
                    a=0;
                }
                else
                {
                    tr[a].f-=tr[a].rf;
                    tr[a].rf=0;
                    maintain(a);
                }
                x=merge(x,a);
                y=merge(_,y);
            }
            if(z)
            {
                split(z,1,b,z);
                split(y,tr[y].siz-1,y,_);
                if(tr[b].col==-1)
                {
                    tr[_].f-=tr[_].rf;
                    tr[_].rf=1;
                    tr[_].f+=tr[_].rf;
                    maintain(_);
                }
                else if(tr[b].col==tr[_].col)
                {
                    tr[_].init(tr[_].col,tr[_].l,tr[b].r,tr[_].lf,tr[b].rf);
                    b=0;
                }
                else
                {
                    tr[b].f-=tr[b].lf;
                    tr[b].lf=0;
                    maintain(b);
                }
                z=merge(b,z);
                y=merge(y,_);
            }
            rt=merge(merge(x,y),z);
        }
        tr[rt].pushfire(1);
        delG(rt);
    }
    return 0;
}

带调试注释版