珂朵莉树,也叫老司机树(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,代码会清爽一些。

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$ 节点。

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 操作那样分离出来,并且挨个修改就完事了。

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<int,int> > 中,第一个元素存储 $v$,第二个存储 $r-l+1$。

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

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

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)\times v^k$ 到答案上。

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 专卡珂朵莉做法。

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

区间推平就是 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;
}
最后修改:2021 年 10 月 27 日
如果觉得我的文章对你有用,请随意赞赏