首页 > 其他 > 详细

浅谈珂朵莉树

时间：2020-02-21 15:19:39      阅读：119      评论：0      收藏：0      [点我收藏+]

序言

珂朵莉是世界上最幸福的女孩。

技术分享图片

\(~\)

珂朵莉树是？

? 老司机树（Old Driver Tree），起源于 CF896C 。出题人 ODT 发明并命名，又名珂朵莉树（Chtholly Tree）。

在学珂朵莉树之前，需要会些啥？

? 需要会 \(\text{C++STL}\) 的 \(\text{set}\) ，在这里博主就简单普及一下 \(\text{set}\) 吧。

  1. \(\text{set}\) 维护的是个不可重集。
  2. \(\text{set}\) 维护的元素是有序的。

? \(\text{set}\) 的内部实现是一棵红黑树（平衡树中速度较快），因此性能不赖。

\(~\)

\(\text{set}\) 的声明 : 

set<数据类型>名字;
/* for example */
set<int>a;
set< pair<int,int> >b;
struct Node{...}; set<Node>c;

\(~\)

\(\text{set}\) 的迭代器 :

? \(\text{set}\) 的迭代器不支持随机访问，只能支持 " ++ " 和 " -- " 来操作迭代器，来看这个片段：

set<int>::iterator it;

? 此时这里的 it 就是迭代器，为了方便，我们常常使用宏定义 #define iter set<数据类型>::iterator ，当然在 \(\text{C++11}\) 下可以直接使用 auto 来代替 iter 。

? 如果 it 是迭代器，那么调用 it++ 会使得 it 指向其在 \(\text{set}\) 中的下一个元素，也就是说，若原本 it 在 \(\text{set}\) 中的排名为 \(k\) ，则调用 it++ 会使得 it 指向排名为 \(k+1\) 的元素。it-- 同理，指向上一个元素。

? " ++ " 和 " -- " 时间复杂度都是 \(\mathcal{O(\log n)}\) 的。

\(~\)

\(\text{set}\) 的插入 :

? 例如我们有一个 \(\text{set}\) 叫做 \(S\) 。

? S.insert(x) 用 \(\mathcal{O(\log n)}\) 的时间将 \(x\) 插入到 \(S\) 中，若 \(S\) 已经维护了 \(x\) ，则不会重复插入 \(x\) ，也就是对 \(S\) 无影响。

S.insert(x);
/* for example */
set< pair<int,int> >S; S.insert(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; S.insert((Node){1,n,114514});

\(~\)

\(\text{set}\) 的删除 :

? 例如我们有一个 \(\text{set}\) 叫做 \(S\) 。

? 若 it 是个迭代器，则 S.erase(it) 用 \(\mathcal{O(\log n)}\) 的时间将 it 指向的元素删去。

? 若 \(x\) 是个元素，则 S.erase(x) 用 \(\mathcal{O(\log n)}\) 的时间将元素 \(x\) 删去，若 \(S\) 没有维护 \(x\) ，则不会删除 \(x\) ，也就是对 \(S\) 无影响。

S.erase(it);
S.erase(x);
/* for example */
set< pair<int,int> >S; S.erase(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; S.erase((Node){1,n,114514});

\(~\)

\(\text{set}\) 的查找 :

? 例如我们有一个 \(\text{set}\) 叫做 \(S\) 。

? S.find(x) 用 \(\mathcal{O(\log n)}\) 的时间查找元素 \(x\) ，并返回该元素的迭代器，若元素 \(x\) 不存在，返回 S.end() 。

? S.lower_bound(x) 用 \(\mathcal{O(\log n)}\) 的时间查找大于等于元素 \(x\) 中最小的一个，并返回指向该元素的迭代器，若不存在，返回 S.end() 。

? S.upper_bound(x) 用 \(\mathcal{O(\log n)}\) 的时间查找大于元素 \(x\) 中最小的一个，并返回该元素的迭代器，若不存在，返回 S.end() 。

S.find(x);
S.lower_bound(x);
S.upper_bound(x);
/* for example */
set< pair<int,int> >S; it=S.find(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; it=S.upper_bound((Node){1,n,114514});

\(~\)

至此 \(\text{set}\) 的操作已经可以用来编写珂朵莉树了。

珂朵莉树还有链表的实现方法，学有余力的读者可以自己去了解一下。

\(~\)

正式了解一下珂朵莉树！

? 珂朵莉树维护的是一堆三元组 \((l,r,val)\) ，其含义是：区间 \([l,r]\) 的值均为 \(val\) 。用 \(\text{set}\) 维护这一堆三元组（按区间顺序排序）。

? 我们发现珂朵莉树的精髓在于：把一段值相同的区间缩成一个三元组处理。

\(~\)

珂朵莉树的声明 :

struct Node{
    int l,r;
    mutable int val;
    Node(int a,int b,int c):l(a),r(b),val(c){}
    inline bool operator < (const Node a) const {
        return l<a.l;
    }
}
set<Node>odt;

\(~\)

split 操作 :

? 有时候，我们想要对一段区间 \([l,r]\) 进行操作或者查询，我们希望正好有若干个段刚好覆盖了区间 \([l,r]\) ，这样我们就可以直接在这些段上面操作了。

? 但是考虑到 \(l\) 和 \(r\) 所在的段，以 \(l\) 为例子，我们设 \(l\) 所在的段为 \([x,y]\) ，我们会发现，只有 \([l,y]\) 这个段是有用的，而我们不需要对 \([x,l)\) 这个段进行任何处理。但是人家两个段偏偏却合在一起，组成了段 \([x,y]\) ！此时我们就要想办法，将段 \([x,y]\) 拆成段 \([x,l)\) 和段 \([l,y]\) 。

? 设函数 \(split(x)\) 表示：将 \(x\) 所在的段 \([L,R]\) 拆成段 \([L,x)\) 和段 \([x,R]\) ，并返回段 \([x,R]\) 的迭代器。

  1. 二分查找 \(x\) 在 \(\text{set}\) 里面所在段的迭代器。
  2. 判断该段的左端点 \(L\) 是否与 \(x\) 重叠，若有，则代表不存在段 \([L,x)\) ，直接返回该迭代器；否则进入 3 。
  3. 删除该迭代器所指向的元素，插入两个三元组 \((L,x-1,val)\) 与 \((x,R,val)\) ，并返回 \((x,R,val)\) 的迭代器。
iter split(int x)
{
    if(x>n)return odt.end(); // 特判
    iter it=--odt.upper_bound((Node){x,0,0});
    if(it->l==x)return it;
    int L=it->l,R=it->r,val=it->val;
    odt.erase(it);
    odt.insert((Node){L,x-1,val});
    return odt.insert((Node){x,R,val}).first;
}

\(~\)

assign 操作 :

? 最最最最最最重要的操作：区间推平。

? 区间推平操作可以使得 ODT 的数据规模迅速减小，是保证复杂度的关键所在，设想一下，我们将整个序列 \([1,n]\) 推平为 \(1\) ，那么整个 \(set\) 只需要维护一个三元组 \((1,n,1)\) 就可以起到维护的作用了。

? 设函数 \(assign(l,r,val)\) 表示：将区间 \([l,r]\) 推平为 \(val\) 。

  1. 令 \(itr=split(r+1),itl=split(l)\) 。
  2. 删除 \(itl\) 到 \(itr\) 之间的所有元素（不含 \(itr\)）。
  3. 插入三元组 \((l,r,val)\) 。
void assign(int l,int r,int val)
{
    iter itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert((Node){l,r,val});
}

\(~\)

其他操作 :

? 其他操作其实也都差不多辣，例如区间加啥的，都可以搞。

iter itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++)
{
    // do what you want.
}

? 当然这个板子不是万能的，需要根据情况应变。

\(~\)

珂朵莉树可以干什么呢？

? 骗分。

? 骗分？

? 骗分！

? 对的，你没有看错，就是骗分。

? 若一个数据结构题，带有区间推平操作，都可尝试使用 ODT 来骗分，虽说 ODT 这种东西随便卡的。例如数据里根本没有区间推平操作，再构造 \(n\) 个长度为 \(1\) 的段，然后全是询问操作，这样的话 ODT 连暴力都不如。

? 若想要保证时间复杂度正确，必要的条件是 " 数据随机 " ，附 证明1 与 证明2，在数据随机的情况下，时间复杂度为 \(\mathcal{O(n \log^2 n)}\)，若改为链表维护，则时间复杂度为 \(\mathcal{O(n \log n)}\)。

? 有良心的出题人一般都会给你设置一档 " 数据随机 " 的部分分。

? 总之使用 ODT 还是谨慎一点好。

\(~\)

好题选讲

? 通过几道题来帮助大家深入理解 ODT 。

CF896C Willem, Chtholly and Seniorious

\[ \texttt{Description} \]

维护一个长度为 \(n\) 的数列，支持 \(4\) 种操作：

  • 1 l r x 将 \(a_l,a_{l+1},...,a_{r-1},a_r\) 加上 \(x\) 。

  • 2 l r x 将 \(a_l,a_{l+1},...,a_{r-1},a_r\) 改为 \(x\) 。
  • 3 l r x 询问区间 \([l,r]\) 的第 \(x\) 小。

  • 4 l r x y 询问 \((\sum\limits_{i=l}\limits^{r}{a_i}^x) \text{mod} \ y\) 。

数据由给定的伪代码生成。
\[ \texttt{Solution} \]

  • 这题是起源题，在这里致敬出题人 ODT （感谢 + 膜拜）。

  • " 数据由给定的伪代码生成 " 暗示了什么？数据随机！我们还发现操作 \(2\) 是熟悉的区间推平操作。

  • 所以这道题是个可以用 ODT 来解决的标准样式（区间推平 + 数据随机）。

  • 对于操作 1 l r x ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来，然后令 \(itl\) 到 \(itr\) 指向的元素的值（第三维 \(val\)）加上 \(x\) 。

  • 对于操作 2 l r x ，基本操作，不多说了。

  • 对于操作 3 l r x ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来，然后依次扫描 \(itl\) 到 \(itr\) ，将指向元素缩成一个二元组 \((val,size)\) 存进一个 \(\text{STLvector}\) 里，这里的第一维 \(val\) 就是该元素维护的值，第二维 \(size\) 就是该元素维护的区间的区间大小（\(r-l+1\)），扫描完成后，将该 \(\text{STLvector}\) 按第一维 \(val\) 从小到大排序，然后依次扫描这些二元组 \((val,size)\) ：

    1. 若 \(k\leq size\) ，说明答案就是当前的 \(val\) ，返回 \(val\) 的值即可。
    2. 若 \(k>size\) ，说明答案应该比当前的 \(val\) 还要大，令 \(k-=size\) ，然后继续扫描。

    最后切记要清空这个 \(\text{STLvector}\) 。

  • 对于操作 4 l r x y ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来，考虑到对于底数相等的数，幂不变，所以我们考虑任意一个三元组 \((l,r,val)\) ，它对答案有 \((r-l+1) \times val^x\) 的贡献，于是我们就可以依次扫描 \(itl\) 到 \(itr\) ，将指向元素对答案的贡献累加进答案中，扫描完即可求出答案了，求幂的过程使用快速幂。

  • 至此此题得到解决。

\[ \texttt{Code} \]

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>

#define RI register int
#define iter set<Node>::iterator

using namespace std;

int power(long long a,int b,int p)
{
    a%=p;
    int ans=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=1ll*ans*a%p;
        a=1ll*a*a%p;
    }
    return ans;
}

long long seed;
int MaxV;

long long rnd()
{
    long long res=seed;
    seed=(seed*7+13)%(1000000007);
    return res;
}

int n,m;

struct Node{
    int l,r;
    mutable long long val;
    Node(int a,int b,long long c):l(a),r(b),val(c){};
    inline bool operator < (const Node a) const {
        return l<a.l;
    }
};

set<Node>odt;

iter split(int x)
{
    if(x>n)return odt.end();
    iter it=--odt.upper_bound((Node){x,0,0});
    if(it->l==x)return it;
    int l=it->l,r=it->r; long long val=it->val;
    odt.erase(it);
    odt.insert((Node){l,x-1,val});
    return odt.insert((Node){x,r,val}).first;
}

void add(int l,int r,int val)
{
    iter itr=split(r+1),itl=split(l);
    for(;itl!=itr;itl++)
        itl->val+=val;
}

void assign(int l,int r,int val)
{
    iter itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert((Node){l,r,val});
}

long long ask_kth(int l,int r,int k)
{
    vector< pair<long long,int> >QAQ;
    iter itr=split(r+1),itl=split(l);
    for(;itl!=itr;itl++)
        QAQ.push_back(make_pair(itl->val,itl->r-itl->l+1));
    sort(QAQ.begin(),QAQ.end());
    for(RI i=0;i<(int)QAQ.size();i++)
    {
        if(k<=QAQ[i].second)return QAQ[i].first;
        else k-=QAQ[i].second;
    }
    return -1;
}

int ask_xpower(int l,int r,int x,int y)
{
    iter itr=split(r+1),itl=split(l);
    int ans=0;
    for(;itl!=itr;itl++)
        ans=(ans+1ll*(itl->r-itl->l+1)*power(itl->val,x,y))%y;
    return ans;
}

int main()
{
    scanf("%d%d%lld%d",&n,&m,&seed,&MaxV);

    for(RI i=1;i<=n;i++)
        odt.insert((Node){i,i,rnd()%MaxV+1});

    while(m--)
    {
        int opt=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;

        if(l>r)
            swap(l,r);

        if(opt==3)
            x=(rnd()%(r-l+1))+1;
        else
            x=(rnd()%MaxV)+1;

        if(opt==4)
            y=(rnd()%MaxV)+1;

        switch(opt)
        {
            case 1:{

                add(l,r,x);

                break;
            }

            case 2:{

                assign(l,r,x);

                break;
            }

            case 3:{

                printf("%lld\n",ask_kth(l,r,x));

                break;
            }

            case 4:{

                printf("%d\n",ask_xpower(l,r,x,y));

                break;
            }
        }
    }

    return 0;
}

[SCOI2010]序列操作

\[ \texttt{Description} \]

维护一个长度为 \(n\) 的 \(0/1\) 序列，支持 \(5\) 种操作：

  • 0 l r 将区间 \([l,r]\) 的所有数改为 \(0\) 。

  • 1 l r 将区间 \([l,r]\) 的所有数改为 \(1\) 。
  • 2 l r 将区间 \([l,r]\) 的所有数取反（\(0\) 变 \(1\) ，\(1\) 变 \(0\)）。
  • 3 l r 询问区间 \([l,r]\) 有多少个 \(1\) 。

  • 4 l r 询问区间 \([l,r]\) 最多有多少个连续的 \(1\) 。

\[ \texttt{Solution} \]

  • 我们发现操作 0 l r 和 1 l r 都是区间推平操作，虽说不保证数据随机，ODT 是假的，但是还是可以通过这题练练 ODT 的。
  • 对于操作 0 1 r 和 1 l r ，基本操作，不多说了。

  • 对于操作 2 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来，然后依次扫描 \(itl\) 到 \(itr\) ，将三元组 \((l,r,val)\) 赋为 \((l,r,val \ \text{xor} \ 1)\) ，即可取反。

  • 对于操作 3 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来，然后依次扫描 \(itl\) 到 \(itr\) ，考虑一个三元组 \((l,r,val)\) ，若 \(val\) 为 \(1\) ，则该三元组对答案有 \(r-l+1\) 贡献，否则贡献为 \(0\) 。依次计算每个三元组的贡献即可。

  • 对于操作 4 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 \([l,r]\) 拆出来。考虑到最后答案的连续的 "\(1\)" 段，定是由 ODT 中若干个连续的节点组成，且这些节点的第三维 \(val\) 都为 \(1\) 。具体的，我们记一个变量 \(sum\) ，若当前扫描到的三元组 \((l,r,val)\) 的第三维 \(val\) 为 \(1\) ，则令 \(sum+=r-l+1\) ，否则我们就尝试用 \(sum\) 去更新答案，再把 \(sum\) 清 \(0\) ，扫描完即可求出答案了。

  • Luogu 管理员加强了数据，卡了 ODT ，在 Luogu 已经过不了了，只能拿到 30pts ......

\[ \texttt{Code} \]

#include<cstdio>
#include<algorithm>
#include<set>

#define RI register int
#define iter set<Node>::iterator

using namespace std;

inline int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}

const int N=100100;

int n,m;

int a[N];

struct Node{
    int l,r;
    mutable int val;
    Node(int a,int b,int c):l(a),r(b),val(c){}
    inline bool operator < (const Node a) const {
        return l<a.l;
    }
};

set<Node>odt; 

iter split(int x)
{
    if(x>n)return odt.end();
    iter it=--odt.upper_bound((Node){x,0,0});
    if(it->l==x)return it;
    int l=it->l,r=it->r,val=it->val;
    odt.erase(it);
    odt.insert((Node){l,x-1,val});
    return odt.insert((Node){x,r,val}).first;
}

void assign(int l,int r,int val)
{
    iter itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert((Node){l,r,val}); 
}

void reverse(int l,int r)
{
    iter itr=split(r+1),itl=split(l);
    for(;itl!=itr;itl++)
        itl->val^=1;
}

int ask_cnt(int l,int r)
{
    iter itr=split(r+1),itl=split(l);
    int ans=0;
    for(;itl!=itr;itl++)
        if(itl->val==1)
            ans+=itl->r-itl->l+1;
    return ans;
}

int ask_wmax(int l,int r)
{
    iter itr=split(r+1),itl=split(l);
    int ans=0,sum=0;
    for(;itl!=itr;itl++)
        if(itl->val==1)
            sum+=itl->r-itl->l+1;
        else
            ans=max(ans,sum),sum=0;
    ans=max(ans,sum);
    return ans;
}

int main()
{
    n=read(),m=read();

    for(RI i=1;i<=n;i++)
        a[i]=read();

    for(RI i=1;i<=n;i++)
        odt.insert((Node){i,i,a[i]});

    while(m--)
    {
        int opt=read(),l=read()+1,r=read()+1;

        switch(opt)
        {
            case 0:{

                assign(l,r,0);

                break;
            }

            case 1:{

                assign(l,r,1);

                break;
            }

            case 2:{

                reverse(l,r);

                break;
            }

            case 3:{

                printf("%d\n",ask_cnt(l,r));

                break;
            }

            case 4:{

                printf("%d\n",ask_wmax(l,r));

                break;
            }
        }
    }

    return 0;
}

[SHOI2015]脑洞治疗仪

\[ \texttt{Description} \]

维护一个长度为 \(n\) 的 \(0/1\) 序列，支持 \(3\) 种操作：

  • 0 l r 将区间 \([l,r]\) 的所有数改为 \(0\) 。
  • 1 l0 r0 l1 r1 将区间 \([l_0,r_0]\) 的所有 "\(1\)" 填到区间 \([l_1,r_0]\) 的 "\(0\)" 上（位置靠前的优先填，多余 \(1\) 弃掉）。
  • 2 l r 询问区间 \([l,r]\) 最多有多少连续的 \(0\) 。

\[ \texttt{Solution} \]

  • 注意到操作 0 l r ，又是区间推平操作，于是我们又可以用 ODT 骗分了
  • 对于 0 l r ，基本操作，不多说了。
  • 对于 1 l0 r0 l1 r1 ，我们先统计出区间 \([l_0,r_0]\) 的 "\(1\)" 个数，记为 \(cnt\) ，随后将区间 \([l_0,r_0]\) 推平为 \(0\) 。接下来是填数部分，调用 itr=split(r1+1),itl=split(l1) ，将区间 \([l_1,r_1]\) 拆出来，然后依次扫描 \(itl\) 到 \(itr\) ，考虑当前扫描到的三元组 \((l,r,val)\) ，若 \(val\) 为 \(1\) ，则继续扫描，否则，记 \(size=r-l+1\)：
    1. 若 \(cnt=0\) ，则不能继续填数了，直接退出。
    2. 若 \(cnt<size\) ，则说明我们只能填该段的一部分（前 \(cnt\) 个数），那我们调用 it=--split(l+cnt) ，就分出了该区间的前 \(cnt\) 个数，将 \(it\) 指向的元素的第三维 \(val\) 改为 \(1\) ，然后退出即可。
    3. 若 \(size \leq cnt\) ，则说明剩下的 "\(1\)" 的个数足够填满这个段，把该段的第三维 \(val\) 改为 \(1\) ，然后我们再令 \(cnt-=size\) ，继续扫描。

  • 对于 2 l r ，上一个例题已经详细讲过了，不多说了。

  • 这题 Luogu 管理员居然没有去卡 ODT ，谢天谢地。

\[ \texttt{Code} \]

#include<cstdio>
#include<algorithm>
#include<set> 

#define RI register int
#define iter set<Node>::iterator

using namespace std;

namespace IO
{
    static char buf[1<<20],*fs,*ft;
    inline char gc()
    {
        if(fs==ft)
        {
            ft=(fs=buf)+fread(buf,1,1<<20,stdin);
            if(fs==ft)return EOF;
        }
        return *fs++;
    }
    #define gc() getchar()
    inline int read()
    {
        int x=0,f=1;char s=gc();
        while(s<'0'||s>'9'){if(s=='-')f=-f;s=gc();}
        while(s>='0'&&s<='9'){x=x*10+s-'0';s=gc();}
        return x*f;
    }
}using IO::read;

const int N=200100;

int n,m;

struct Node{
    int l,r;
    mutable bool val;
    Node(int a,int b,int c):l(a),r(b),val(c){}
    inline bool operator < (const Node a) const {
        return l<a.l;
    }
};

set<Node>odt;

iter split(int x)
{
    if(x>n)return odt.end();
    iter it=--odt.upper_bound((Node){x,0,0});
    if(it->l==x)return it;
    int l=it->l,r=it->r; bool val=it->val;
    odt.erase(it);
    odt.insert((Node){l,x-1,val});
    return odt.insert((Node){x,r,val}).first;
}

void assign(int l,int r,int val)
{
    iter itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert((Node){l,r,val});
}

void trans(int l0,int r0,int l1,int r1)
{
    iter itr0=split(r0+1),itl0=split(l0);
    int cnt=0;
    for(iter i=itl0;i!=itr0;i++)
        if(i->val)cnt+=i->r-i->l+1;
    odt.erase(itl0,itr0);
    odt.insert((Node){l0,r0,0});
    iter itr1=split(r1+1),itl1=split(l1);
    for(iter i=itl1;i!=itr1;i++)
    {
        if(i->val)continue;
        if(i->r-i->l+1<=cnt)
            i->val=true,cnt-=i->r-i->l+1;
        else
        {
            if(cnt)
            {
                iter it=--split(i->l+cnt);
                it->val=true;
            }
            break;
        }
    }
}

int ask_wmax(int l,int r)
{
    iter itr=split(r+1),itl=split(l);
    int ans=0,sum=0;
    for(;itl!=itr;itl++)
        if(itl->val)
            ans=max(ans,sum),sum=0;
        else
            sum+=itl->r-itl->l+1;
    return max(ans,sum);
}

int main()
{
    n=read(),m=read();

    odt.insert((Node){1,n,1});

    while(m--)
    {
        int opt=read(),l=read(),r=read(),l1,r1;

        switch(opt)
        {
            case 0:{

                assign(l,r,0);

                break;
            }

            case 1:{

                l1=read(),r1=read();

                trans(l,r,l1,r1);

                break;
            }

            case 2:{

                printf("%d\n",ask_wmax(l,r));

                break;
            }
        }
    }

    return 0;
}

（可能还会有题，先挖个坑。

\(~\)

结语

? 正如上文提及到的，珂朵莉树是一个强大的骗分算法，若有一道数据结构题，满足 " 带有区间推平 " 和 " 数据随机 " ，这两个条件，则珂朵莉树是一个不二的选择。

? 总之使用珂朵莉树需谨慎，毕竟这玩意可以随便卡的。

? 希望博主的这篇文章对大家有帮助。
\[ \texttt{Thanks} \ \texttt{for} \ \texttt{watching} \]

浅谈珂朵莉树

原文：https://www.cnblogs.com/cjtcalc/p/12340753.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！