Loading...

珂朵莉树笔记

check评论:0 条 remove_red_eye浏览量:108 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2019-08-22

然而本人并不喜欢珂朵莉

珂朵莉树是一种暴力数据结构,即用$set$维护权值相同的区间,所以在有区间赋值和数据随机的题目中有较大优势

来一步步分析珂朵莉树的操作

我们先考虑怎么储存节点

珂朵莉树需要保存的信息有区间左右端点,以及当前权值等,写起来非常简单

struct node
{
    int l,r;
    mutable ll v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const node&a)const
    {
        return l<a.l;
    }
};

其中$mutable$意思是可变的

首先,将$set$中一个节点进行拆分,即$split$,主要用于修改一个大区间中的一部分

我们先找到改节点的前驱,然后从这里进行拆分即可

#define IT set<node>::iterator
IT split(int pos)
{
    IT it=st.lower_bound(node(pos));
    if(it!=st.end()&&it->l==pos)
    {
        return it; 
    }
    --it;
    ll V=it->v;
    int L=it->l,R=it->r;
    st.erase(it);
    st.insert(node(L,pos-1,V));
    return st.insert(node(pos,R,V)).first;
}

如果只有$split$,那么块会越来越多,复杂度会趋近$O(n)$,我们需要减少块的数量,就用到了函数$assign$,每次出现区间赋值操作后,我们就可以将这中间的所有区间$assign$成一个区间,由于数据随机,$assign$操作会较多,复杂度会趋近于$O(nlogn)$

void assign(int l,int r,int val)
{
    IT itr=split(r+1),itl=split(l);
    st.erase(itl,itr);
    st.insert(node(l,r,val));
}

然后剩下的操作就很暴力了

比如区间加法,就是

void add(int l,int r,int x)
{
    IT itr=split(r+1),itl=split(l);
    while(itl!=itr)
    {
        itl->v+=x;
        ++itl;
    }
}

其他的都是差不多的套路

然后给出一道例题

$code:$

/**************************/
/*It is made by decoration*/
/*gzzkal   gzzkal   gzzkal*/
/*It is made by decoration*/
/**************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    int l,r;
    mutable ll v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const node&a)const
    {
        return l<a.l;
    }
};
set<node> st;
#define IT set<node>::iterator
IT split(int pos)
{
    IT it=st.lower_bound(node(pos));
    if(it!=st.end()&&it->l==pos)
    {
        return it; 
    }
    --it;
    ll V=it->v;
    int L=it->l,R=it->r;
    st.erase(it);
    st.insert(node(L,pos-1,V));
    return st.insert(node(pos,R,V)).first;
}
void assign(int l,int r,int val)
{
    IT itr=split(r+1),itl=split(l);
    st.erase(itl,itr);
    st.insert(node(l,r,val));
}
void make1(int l,int r)
{
    assign(l,r,1);
}
void make0(int l,int r)
{
    assign(l,r,0);
}
void getrev(int l,int r)
{
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        itl->v^=1;
    }
}
int getsum(int l,int r)
{
    IT itr=split(r+1),itl=split(l);
    int ans=0;
    for(;itl!=itr;++itl)
    {
        ans+=(itl->r-itl->l+1)*itl->v;
    }
    return ans;
}
int getl(int l,int r)
{
    int ans=0,now=0;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        if(itl->v==0)
        {
            ans=max(ans,now);
            now=0;
        }
        else
        {
            now+=(itl->r-itl->l+1);
        }
    }
    return max(ans,now);
}
int main()
{
    int n,m,last,lf,x;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i==1)
        {
            last=x,lf=1;
            continue;
        }        
        if(x==last)
        {
            continue;
        }
        st.insert(node(lf,i-1,last));
        last=x,lf=i; 
    }
    st.insert(node(lf,n,last));
    st.insert(node(n+1,n+1,0));
    for(int i=1;i<=m;i++)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        ++l,++r;
        switch(opt)
        {
            case 0:make0(l,r);break;
            case 1:make1(l,r);break;
            case 2:getrev(l,r);break;
            case 3:printf("%d\n",getsum(l,r));break;
            case 4:printf("%d\n",getl(l,r));break;
        }
    }
}

最后提一下这种数据结构的发源题目

不给代码了,不然篇幅过长了

chevron_left CF915E 题解
数论小结 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名