珂朵莉树,也叫老司机树($Old-Driver-Tree$),起源自$CF896C$


前置知识:$STL::set$以及手。

严格来说,这并不是一种数据结构,而是一种暴力骗分的技巧。

珂朵莉树可以优雅且高效地处理随机数据下的(区间赋值,区间修改,区间$K-th$,区间$k$次幂和)操作。

听起来是不是很舒服的一种算法?然而它的时间复杂度只在随机数据下正确。所以特殊构造的数据完全可以卡掉$ODT$。它适合在特殊构造数据时作为一种暴力来对拍/骗分。

不知道其他初学者怎么样,反正珂朵莉树是秀了我一脸。


为什么说它暴力?来看看它的操作过程。

它的节点保存很特殊,包含三个关键字$l,r,v$,表示区间$[l,r]$全部为$v$。并且节点将全部压到一个$STL::set$中。

特殊的是,因为要对其中的$v$在$set$中进行修改(区间修改),所以需要用到一种骚操作,这样定义一个节点:

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

可以注意到有个 multable ll v。它的作用是突破$const$的限制,让它放在$set$中也可以被直接修改,并且永远可变

以下是正片。


注:(*it).v等同于 it->v,蒟蒻我只是不想用指针,看着不顺眼。

初始化

根据定义,每个节点初始为$\{i,i,val[i]\}$。构造并压入$set$。

split操作

以下操作的基础。

即把一个包含$pos$的区间$[l,r]$断成两个区间$[l,pos-1],[pos,r]$,并且返回指向后者的迭代器。

这就开始体现出它的暴力了:直接二分找到这个区间$[l,r]$,并且删除它,再加入新的两个区间。

我人傻了都

首先 #define IT set<node>::iterator,代码会清爽一些。

inline 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;
    ll v=(*it).v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).f;
}

特判的原因是,如果找到的区间不是最后一个,并且它恰好包含$pos$,那么当前已经完成了$[l,pos-1],[pos,r]$的拆分,就不需要再进行不必要的操作了。

值得一提的是,$set$的$insert$操作会返回一个$pair<iterator,bool>$,前者代表指向新插入元素的迭代器,后者代表是否插入成功,于是利用这个特性直接返回即可。

assign操作

即区间赋值操作。把$[l,r]$都修改为$v$。

这个就更暴力了。

先把原来的$[l,r]$删掉,再新加入进去一个$\{l,r,v\}$就完成了。

怎么删掉?先利用$split$把$l,r$分别独立出来,再利用$set$的区间删除(给定迭代器$l,r$,删除区间$[l,r)$)把它删掉再加入新的。由于删除区间是左闭右开的,于是我们$split(r+1)$即可。注意要先$split(r+1)$,再$split(l)$,否则可能在$split(l)$时删除掉$r+1$节点。

inline void assign(int l,int r,ll v)
{
    IT ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(node(l,r,v));
}

是真的短


add操作

即区间加操作。可以轻松改为区间乘、减等(指只改动一个符号)。

最暴力的一个操作。

把$[l,r]$像$assign$操作那样分离出来,并且挨个修改就完事了。

inline void add(int l,int r,ll v)
{
    IT ir=split(r+1),il=split(l);
    while(il!=ir)
    {
        (*il).v+=v;
        il++;
    }
}

rank操作

即区间$K-th$操作。

还是暴力暴力暴力。

把区间$[l,r]$分离出来,并把其中包含的每个$\{l,r,v\}$压到一个$vector<pair>$中,第一个元素存储$v$,第二个存储$r-l+1$。

然后...直接对$vector$按照$v$排序。。

接着每遍历一个元素,就用$k$减去它对应的长度,直到$k\leq0$时的$v$即为答案。

inline ll rk(int l,int r,ll k)
{
    vector<pi> v;
    v.clear();
    IT ir=split(r+1),il=split(l);
    while(ir!=il)
    {
        v.push_back(make_pair((*il).v,(*il).r-(*il).l+1));
        il++;
    }
    sort(v.begin(),v.end());
    for(vector<pi>::iterator it=v.begin();it!=v.end();it++)
    {
        k-=(*it).s;
        if(k<=0)return (*it).f;
    }
    return -1;
}

sum操作

即区间$k$次幂求和操作。

不想说了,每个操作都那么暴力。

把$[l,r]$分离出来,对于每个$\{l,r,v\}$,累加$(r-l+1)*pow(v,k)$到答案上,$pow$用快速幂实现即可。

inline ll sum(int l,int r,ll k,ll p)
{
    IT ir=split(r+1),il=split(l);
    ll res=0;
    while(il!=ir)
    {
        res+=((*il).r-(*il).l+1)*qpow((*il).v,k,p)%p;
        res%=p;
        il++;
    }
    return res;
}

整题代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<ll,int>
#define f first
#define s second
#define IT set<node>::iterator
using namespace std;
inline ll qpow(ll a,ll b,ll p)
{
    ll x=a%p,ans=1;
    while(b)
    {
        if(b&1)(ans*=x)%=p;
        (x*=x)%=p;
        b>>=1;
    }
    return ans;
}
ll seed;
int vmax;
inline ll rnd()
{
    ll res=seed;
    seed=(seed*7+13)%1000000007;
    return res;
}
struct node
{
    int l,r;
    mutable ll v;
    node(int L,int R=-1,ll V=0):l(L),r(R),v(V){}
    bool operator < (const node &x) const {return l<x.l;}
};
set<node> s;
inline 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;
    ll v=(*it).v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).f;
}
inline void assign(int l,int r,ll v)
{
    IT ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(node(l,r,v));
}
inline void add(int l,int r,ll v)
{
    IT ir=split(r+1),il=split(l);
    while(il!=ir)
    {
        (*il).v+=v;
        il++;
    }
}
inline ll rk(int l,int r,ll k)
{
    vector<pi> v;
    v.clear();
    IT ir=split(r+1),il=split(l);
    while(ir!=il)
    {
        v.push_back(make_pair((*il).v,(*il).r-(*il).l+1));
        il++;
    }
    sort(v.begin(),v.end());
    for(vector<pi>::iterator it=v.begin();it!=v.end();it++)
    {
        k-=(*it).s;
        if(k<=0)return (*it).f;
    }
    return -1;
}
inline ll sum(int l,int r,ll k,ll p)
{
    IT ir=split(r+1),il=split(l);
    ll res=0;
    while(il!=ir)
    {
        res+=((*il).r-(*il).l+1)*qpow((*il).v,k,p)%p;
        res%=p;
        il++;
    }
    return res;
}
inline ll read()
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
int main()
{
    ll n=read(),m=read();
    seed=read(),vmax=read();
    for(int i=1;i<=n;i++)
        s.insert((node){i,i,rnd()%vmax+1});
    for(int i=1;i<=m;i++)
    {
        ll 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()%vmax+1;
        if(opt==4)y=rnd()%vmax+1;
        if(opt==1)
            add(l,r,x);
        else if(opt==2)
            assign(l,r,x);
        else if(opt==3)
            printf("%lld\n",rk(l,r,x));
        else if(opt==4)
            printf("%lld\n",sum(l,r,x,y));
    }
    return 0;
}

骗分例题

洛谷$P4979$ 矿洞:坍塌

前排提示:不开$O2$就会炸,仅练习$ODT$而已。

大致题意:

两个操作:

1.格式$A$ $x$ $y$ $op$,表示把$[l,r]$修改为$op$。

2.格式$B$ $x$ $y$,表示查询$[l,r]$是否合法。合法的定义为:区间内元素全部相同,且区间左右两边的元素不同。

区间赋值直接上就好了,查询是否合法就扫一遍,发现有不等就$No$,如果都等,那么判断两边相等就$No$,不等就$Yes$。

常数卡不进不开$O2$就能过的境界,所以。。

代码:

#include<bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
inline int read()
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
struct node
{
    int l,r;
    mutable int v;
    node(int l,int r=-1,int v=0):l(l),r(r),v(v){}
    bool operator < (const node &x)const{return l<x.l;}
};
set<node> s;
inline 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,v=(*it).v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;
}
inline void assign(int l,int r,int v)
{
    IT ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(node(l,r,v));
}
int n,k;
inline bool check(int l,int r)
{
    IT ir=split(r+1),tmp=split(l);
    ir--;
    IT il=tmp;
    while(il!=ir)
    {
        if((*il).v!=(*ir).v)return 0;
        il++;
    }
    if(l==1||r==n)return 1;
    il=tmp;
    il--,ir++;
    return (*il).v!=(*ir).v;
}
char a[500010];
char op[10010];
int main()
{
    n=read();
    scanf("%s",a);
    for(int i=0;i<n;i++)
    {
        int num=a[i]-'A'+1;
        s.insert(node(i+1,i+1,num));
    }
    k=read();
    for(int i=1;i<=k;i++)
    {
        scanf("%s",a);
        int x=read(),y=read();
        if(a[0]=='A')
        {
            scanf("%s",op);
            assign(x,y,op[0]-'A'+1);
        }
        else
            puts(check(x,y)?"Yes":"No");
    }
    return 0;
}

洛谷P2787 语文1(chin1)-理理思维

原题不卡珂朵莉,#13专hack珂朵莉做法。

精心构造的肯定卡不过去呗...就讲讲思路。

区间推平就是$assign$操作。

区间查询单个出现次数,也是把这个区间分出来,如果遍历到$\{l,r,v\}$的$v$符合要求,那么 cnt+=(r-l+1);

区间排序。直接sort肯定是要超时的,考虑到元素只有$26$个,一发桶排再放回去即可。正好可以缩小节点规模。

代码:(过不了#13)

#include<bits/stdc++.h>
#define IT set<node>::iterator
#define f first
#define s second
using namespace std;
struct node
{
    int l,r;
    mutable int v;
    node(int l,int r=-1,int v=0):l(l),r(r),v(v){}
    bool operator < (const node &x)  const {return l<x.l;}
};
set<node> s;
inline int read()
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline 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,v=it->v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).f;
}
inline void assign(int l,int r,int v)
{
    IT ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(node(l,r,v));
}
inline int find(int l,int r,int v)
{
    int cnt=0;
    IT ir=split(r+1),il=split(l);
    while(il!=ir)
    {
        if(il->v==v)cnt+=(il->r-il->l+1);
        il++;
    }
    return cnt;
}
inline void gsort(int l,int r)
{
    IT ir=split(r+1),il=split(l);
    IT ill=il;
    int a[27];
    memset(a,0,sizeof a);
    while(il!=ir)
    {
        a[il->v]+=(il->r-il->l+1);
        il++;
    }
    s.erase(ill,ir);
    for(int i=0;i<26;i++)
        if(a[i])
        {
            s.insert(node(l,l+a[i]-1,i));
            l+=a[i];
        }
}
char sr[10];
char a[100010];
int main()
{
    int n=read(),m=read();
    scanf("%s",a);
    int len=strlen(a);
    for(int i=0;i<len;i++)
    {
        if(a[i]>'Z')a[i]-=('a'-'A');
        s.insert(node(i+1,i+1,a[i]-'A'));
    }
    while(m--)
    {
        int opt=read(),x=read(),y=read();
        if(opt==1)
        {
            scanf("%s",sr);
            if(sr[0]>'Z')sr[0]-=('a'-'A');
            printf("%d\n",find(x,y,sr[0]-'A'));
        }
        if(opt==2)
        {
            scanf("%s",sr);
            if(sr[0]>'Z')sr[0]-=('a'-'A');
            assign(x,y,sr[0]-'A');
        }
        if(opt==3)
            gsort(x,y);
    }
    return 0;
}
最后修改:2020 年 08 月 17 日 08 : 09 PM