UOJ Logo xukuan的博客

博客

珂朵莉树

2019-11-06 16:30:50 By xukuan

参考文章

https://www.luogu.org/blog/aaronlee/solution-cf896c

https://www.luogu.org/blog/ACdreamer/solution-cf896c

作用

珂朵莉树是一个可以维护随机数据下区间x次方和查询的数据结构。

在数据随机的时候推平操作比较多，所以它的复杂度会趋近于$mlog_2 n$（m为询问次数）。这个跟我水ddp模板的思想很类似。

所以珂朵莉树的主要作用是骗分

如果不知道这些的话。。。昨天机房里坐在我左边的x义x大佬就出了笑话

上两张图大家理解一下：

x义x：

结果：

（此题满分1000分）

节点定义

struct node{
    ll l,r;
    mutable ll val;
    node(ll L,ll R=-1,ll Val=0):l(L),r(R),val(Val){}
    inline bool operator <(const node &x)const{
        return l<x.l;
    }
};
#define set_node_it set<node>::iterator
set<node> s;

我们定义一个三元组$(l,r,val)$来表示区间$[l,r]$内的数的值全都是$val$。关于$mutable$，意为易变的，不定的。它对$val$的修饰，使得我们可以在$update$操作中修改$val$的值。没有它的修饰会在$update$函数里导致CE。

初始化

大概就是一个套路，本题是这样的：

cin>>n>>m>>seed>>vmax;
for(ll i=1; i<=n; i++){
    a[i]=(rnd()%vmax)+1;
    s.insert(node(i,i,a[i]));
}

时间复杂度以及卡常

$O(m log_2 n)$。由于数据随机，期望有一部分的操作为assign，set的大小趋于$log_2 n$，因此这种数据结构复杂度接近$m log_2 n$。

但是珂朵莉树的常数非常大（毕竟set是STL三大乌龟set,map,complex之一），写的时候要注意常数以及一些特殊性质。

各种操作

操作的时候一定要注意，必须写$set\_node\_it \space R=split(r+1),L=split(l)$，不能写$set\_node\_it \space L=split(l),R=split(r+1)$，因为在split中，我们存在一个erase操作，可能会改变前面l的值，这样会出错（但这题并没有）

核心操作：分裂 split

$split(x)$是指将原来含有$x$的区间$[l,r]$分成两部分：$[l,x)$和$[x,r]$

有点类似fhqtreap的split操作

代码：

inline set_node_it split(ll x){
    set_node_it i=s.lower_bound(node(x));
    if(i!=s.end()&&i->l==x) return i;
    i--;
    ll l=i->l,r=i->r,val=i->val;
    s.erase(i);
    s.insert(node(l,x-1,val));
    return s.insert(node(x,r,val)).first;
}

推平 assign

显然，把$[l,r]$这段区间里的点全删了然后加一个点$(l,r,val)$进去

代码：

inline void assign(ll l,ll r,ll val){
    set_node_it R=split(r+1),L=split(l);
    s.erase(L,R);
    s.insert(node(l,r,val));
}

区间和

不解释

inline ll getsum(ll l,ll r,ll ex,ll mod){
    ll ans=0;
    for(set_node_it R=split(r+1),L=split(l); L!=R; L++) ans=(ans+(L->r-L->l+1)*ksm(L->val%mod,ex,mod))%mod;
    return ans;
}

区间第k小：

暴力取出排序，同样不解释

inline ll getvalbyrank(ll l,ll r,ll rank){
    vector<pLL> G; G.clear();
    for(set_node_it R=split(r+1),L=split(l); L!=R; L++) G.push_back(make_pair(L->val,L->r-L->l+1));
    sort(G.begin(),G.end());
    for(ll i=0; i<G.size(); i++){
        rank-=G[i].second;
        if(rank<=0) return G[i].first;
    }
    return -1;
}

例题

CF896C

珂朵莉树的板子，上面的东西组合起来就行了

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
#define set_node_it set<node>::iterator
#define pLL pair<ll,ll>
using namespace std;

const ll N=100010,mod=1000000007;
ll n,m,seed,vmax,a[N];

inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<3)+(y<<1);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}

ll ksm(ll x,ll y,ll mod){
    if(y==0) return 1;
    ll t=ksm(x,y/2,mod)%mod;
    t=t*t%mod;
    if(y&1) t=t*x%mod;
    return t;
}

inline ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%mod;
    return ret;
}

namespace ODT{
    struct node{
        ll l,r;
        mutable ll val;
        node(ll L,ll R=-1,ll Val=0):l(L),r(R),val(Val){}
        inline bool operator <(const node &x)const{
            return l<x.l;
        }
    };
    set<node> s;
    inline set_node_it split(ll x){
        set_node_it i=s.lower_bound(node(x));
        if(i!=s.end()&&i->l==x) return i;
        i--;
        ll l=i->l,r=i->r,val=i->val;
        s.erase(i);
        s.insert(node(l,x-1,val));
        return s.insert(node(x,r,val)).first;
    }
    inline void update(ll l,ll r,ll val){
        for(set_node_it R=split(r+1),L=split(l); L!=R; L++) L->val+=val;
    }
    inline void assign(ll l,ll r,ll val){
        set_node_it R=split(r+1),L=split(l);
        s.erase(L,R);
        s.insert(node(l,r,val));
    }
    inline ll getvalbyrank(ll l,ll r,ll rank){
        vector<pLL> G; G.clear();
        for(set_node_it R=split(r+1),L=split(l); L!=R; L++) G.push_back(make_pair(L->val,L->r-L->l+1));
        sort(G.begin(),G.end());
        for(ll i=0; i<G.size(); i++){
            rank-=G[i].second;
            if(rank<=0) return G[i].first;
        }
        return -1;
    }
    inline ll getsum(ll l,ll r,ll ex,ll mod){
        ll ans=0;
        for(set_node_it R=split(r+1),L=split(l); L!=R; L++) ans=(ans+(L->r-L->l+1)*ksm(L->val%mod,ex,mod))%mod;
        return ans;
    }
}

int main(){
    cin>>n>>m>>seed>>vmax;
    for(ll i=1; i<=n; i++){
        a[i]=rnd()%vmax+1;
        ODT::s.insert(ODT::node{i,i,a[i]});
    }
    ODT::s.insert(ODT::node{n+1,n+1,0});
    while(m--){
        ll op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;
        if(l>r) swap(l,r);
        if(op==3) x=rnd()%(r-l+1)+1;
        else x=rnd()%vmax+1;
        if(op==4) y=rnd()%vmax+1;
        switch(op){
            case 1:{
                ODT::update(l,r,x);
                break;
            }
            case 2:{
                ODT::assign(l,r,x);
                break;
            }
            case 3:{
                write(ODT::getvalbyrank(l,r,x)); putchar('\n');
                break;
            }
            case 4:{
                write(ODT::getsum(l,r,x,y)); putchar('\n');
                break;
            }
        }
    }
    return 0;
}

CF915E

这个题就有一点小优化了

首先裸的珂朵莉树会一直TLE on #30，那么我们需要优化

我们发现这题只有assign和getsum两种操作，而且getsum的区间一定$[1,n]$。那么我们能否把getsum合并进assign里面呢？

显然是可以的，我们用sum记下当前的和，在每次assign的时候，直接修改sum的值，可以通过此题

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;

int n,m,sum;

namespace ODT{
    struct node{
        int l,r;
        mutable int val;
        node(int L,int R=-1,int Val=0):l(L),r(R),val(Val){}
        inline bool operator <(const node &x)const{
            return l<x.l;
        }
        #define set_node_it set<node>::iterator
    };
    set<node> s;
    inline set_node_it split(int x){
        set_node_it i=s.lower_bound(node(x));
        if(i!=s.end()&&i->l==x) return i;
        i--;
        int l=i->l,r=i->r,val=i->val;
        s.erase(i);
        s.insert(node(l,x-1,val));
        return s.insert(node(x,r,val)).first;
    }
    inline void assign(int l,int r,int val){
        set_node_it R=split(r+1),L=split(l);
        for(set_node_it i=L; i!=R; i++) sum-=i->val*(i->r-i->l+1);
        s.erase(L,R);
        s.insert(node(l,r,val));
        sum+=val*(r-l+1);
    }
}

int main(){
    scanf("%d %d",&n,&m); sum=n;
    ODT::s.insert(ODT::node(1,n,1));
    while(m--){
        int l,r,op; scanf("%d %d %d",&l,&r,&op);
        if(op==1) ODT::assign(l,r,0);
        if(op==2) ODT::assign(l,r,1);
        printf("%d\n",sum);
    }
    return 0;
}

BZOJ4293

这题则需要转变一下维护方式。

我们发现每次收割就是assign

每次的增加就是update，但暴力加会超时

怎么办呢？

我们发现这题各个东西的顺序对答案是没有影响的，所以我们可以按生长速度从小到大排序，然后每次砍过后，二分从哪个点开始砍，时间复杂度$O(m log_2^2 n)$

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=500010;
ll n,m,a[N],d[N],b[N],sum[N];

inline ll read(){
    ll x=0,tmp=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') tmp=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return tmp*x;
}

inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<3)+(y<<1);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}

namespace ODT{
    struct node{
        ll l,r,w;
        mutable ll val;
        node(ll L=0,ll R=0,ll W=0,ll Val=0):l(L),r(R),w(W),val(Val){}
        inline bool operator <(const node &x)const{
            return l<x.l;
        }
        #define set_node_it set<ODT::node>::iterator
    };
    set<node> s;

    inline set_node_it split(ll x){
        set_node_it i=s.lower_bound(x);
        if(i->l==x) return i;
        i--;
        ll l=i->l,r=i->r,w=i->w,val=i->val;
        s.erase(i);
        s.insert(node(l,x-1,w,val));
        return s.insert(node(x,r,w,val)).first;
    }

    inline void query(ll x,ll w){
        ll ans=0;
        for(set_node_it i=split(x); i!=s.end(); i++) ans+=(i->r-i->l+1)*i->val+(sum[i->l]-sum[i->r+1])*(d[w]-d[i->w])-(i->r-i->l+1)*b[w];
        write(ans);
        set_node_it i=split(x);
        s.erase(i,s.end());
        s.insert(node(x,n,w,b[w]));
    }
}

int main(){
    n=read(); m=read();
    for(ll i=1; i<=n; i++) a[i]=read();
    sort(a+1,a+1+n);
    for(ll i=n; i>=1; i--) sum[i]=sum[i+1]+a[i];
    ODT::s.insert(ODT::node(1,n,0,0));
    for(ll i=1; i<=m; i++){
        d[i]=read(); b[i]=read();
        ll l=1,r=n+1,ans=n+1;
        while(l<=r){
            ll mid=(l+r)>>1;
            set_node_it j=ODT::s.upper_bound(mid); j--;
            if(a[mid]*(d[i]-d[j->w])+j->val>=b[i]){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        if(l<n+1) ODT::query(ans,i);
        else putchar('0');
        putchar('\n');
    }
    return 0;
}

评论

Qingyu
膜xukuan
zzt_
orz

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

Server time: 2024-04-25 18:11:47 | 开源项目