珂朵莉树学习笔记

$What is it$

珂朵莉树是一种基于$set$的暴力数据结构,真的很好懂(因为暴力鸭).又叫$Old Driver Tree$,老司机树$???$

$What is it for$

适用于区间赋值,数据随机.

$How to Write it$

首先来讲讲它的思想,它把区间$[1,n]$分成若干个$[l_i,r_i]$,$[l_i,r_i]$内的数都一样,为$w_i$.举栗子!区间$[1,5]$的初值为$1$.现在只有一个区间就是$[1,5],w=1$.然后要求把$[2,4]$区间赋为$2$,于是把区间$[1,5]$拆成$[1,1],[2,4],[5,5]$,再把区间$[2,4]$的$w$赋为$2$.差不多就是这样真的很好懂鸭.下面讲$Code$.

定义$ovo$

struct node
{
    int l,r;//表示[l,r]的区间内值都是w
    mutable int w; //mutble"可变的",与const相对
    node(int ll,int rr=-1,int ww=0){l=ll,r=rr,w=ww;}//赋初值
    inline bool operator<(const node&x)const{return l<x.l;}//重载小于号,按区间左端点从小到大排序
};
set<node>q;

核心操作$assign$

就是把$[l,r]$区间赋值为$w$.

#define IT set<node>::iterator
inline void assign(int l,int r,int w)
{
    IT R=split(r+1),L=split(l);
    //split函数就是把一个迭代器拆成两个并返回后面一个迭代器,后面会讲,也可以先看后面再回来看这里
    q.erase(L,R);
    q.insert(node(l,r,w));
}

首先把包含$l,r$的迭代器拆成分别两个部分$[ ,l-1],[l, ],[ ,r],[r+1, ]$,然后把区间$[l,r]$间的全部去掉,最后$insert$新的区间就$OK$辣.再讲两个细节.

1.必须要先$split(r+1)$,再$split(l)$.因为如果反过来$split(l)$返回的迭代器可能失效导致$CE$.举个栗子,当前$l,r$都包含在$[L,R]$中,首先$split(l)$,变成$[L,l-1],[l,R]$,返回的迭代器是$[l,R]$的.然后$split(r+1)$,又会把$[l,R]erase$掉...

2.$<set>$中的$erase$函数.$q.erase(L,R)$清除掉的是$[L,R)$,是左闭右开!!这里的$R$是$L_i=r+1$的迭代器,所以清除掉的正好是$[l,r]$之间所有的.

核心操作$split$

inline IT split(int p)
{
    IT qwq=q.lower_bound(node(p));
    if(qwq!=q.end() && qwq->l==p)return qwq;//不需要拆分
    --qwq;
    int ll=qwq->l,rr=qwq->r,ww=qwq->w;
    q.erase(qwq);
    q.insert(node(ll,p-1,ww));
    return q.insert(node(p,rr,ww)).first;
}

这里只要解释一下最后一句的意思辣.$q.insert(...).first$就是插入新元素后新元素的迭代器,这时候就会想有$first$,那也有$second$叭.没错!$second$的意思呢就是插入成功了没有.什么时候插入不成功?当$set$里已经有了这个元素时就不能在插入一样的了.($set$中元素不重)

 对了,这里是我参考的优秀清楚的$blog$

$over!$

板子题!

$Luogu2572 [SCOI2010]$序列操作

唯一要注意的是$4$操作,最多有多少个连续的$1$,可能$[l_1,r_1],[l_2,r_2],l_2=r_1+1$这两个区间都$w=1$,可以连续起来.千万不能枚举区间,然后直接取$ret=max(ret,i->r-i->l+1)$,要考虑能否和前面的区间连起来.

#include<bits/stdc++.h>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;i++)
#define yes(i,a,b) for(Rg int i=a;i>=b;i--)
#define IT set<node>::iterator
#define db double
using namespace std;
il int read()
{
    int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*y;
}
const int N=1e5+10;
int n,m;
struct node
{
    int l,r;
    mutable int w;
    node(int ll,int rr=-1,int ww=0){l=ll,r=rr,w=ww;}
    inline bool operator<(const node&x)const{return l<x.l;}
};
set<node>q;
inline IT split(int p)
{
    IT qwq=q.lower_bound(node(p));
    if(qwq!=q.end() && qwq->l==p)return qwq;
    --qwq;
    int ll=qwq->l,rr=qwq->r,ww=qwq->w;
    q.erase(qwq);
    q.insert(node(ll,p-1,ww));
    return q.insert(node(p,rr,ww)).first;
}
inline void assign(int l,int r,int w)
{
    IT R=split(r+1),L=split(l);
    q.erase(L,R);
    q.insert(node(l,r,w));
}
il void sol1(int l,int r)
{
    IT R=split(r+1),L=split(l);
    for(IT i=L;i!=R;i++){Rg int qwq=i->w;i->w=1-qwq;}
}
il int sol2(int l,int r)
{
    IT R=split(r+1),L=split(l);Rg int ret=0;
    for(IT i=L;i!=R;i++){if(i->w==1)ret+=(i->r)-(i->l)+1;}
    return ret;
}
il int sol3(int l,int r)
{
    IT R=split(r+1),L=split(l);Rg int ret=0,qwq=0;
    for(IT i=L;i!=R;i++){if(i->w==1)qwq+=(i->r)-(i->l)+1;else qwq=0;ret=max(ret,qwq);}
    return ret;    
}
int main()
{
    n=read(),m=read();Rg int qwq,pos=1;
    go(i,1,n)
    {
        if(i==1)qwq=read();
        else if(i==n)
        {
            Rg int qvq=read();
            if(qwq==qvq)q.insert(node(pos,i,qwq));
            else {q.insert(node(pos,i-1,qwq)),q.insert(node(i,i,qvq));}
        }
        else
        {
            Rg int qvq=read();
            if(qvq==qwq)continue;
            q.insert(node(pos,i-1,qwq));qwq=qvq,pos=i;
        }
    }
    //print();
    go(i,1,m)
    {
        Rg int op=read(),l=read()+1,r=read()+1;
        if(op==0 || op==1)assign(l,r,op);
        else if(op==2)sol1(l,r);
        else if(op==3)printf("%d
",sol2(l,r));
        else if(op==4)printf("%d
",sol3(l,r));
    }
    return 0;
}

$CF343D Water Tree$