珂朵莉树

Why Chtholly

因为这个数据结构来源于CF896C,所以叫做珂朵莉树（又名ODT（Old Driver Tree））

操作主要有：

• 区间加
• 将区间内所有树改为x
• 输出区间第k大
• 输出[l,r]区间的 $\sum_{i=l}^ra_x^i \mod y$

How To use Chtholly

太暴力了和珂朵莉一点关系都没有

构建一颗Chtholly Tree:

struct Node{
    int l,r;
    mutable int val;
    Node(int ll,int rr = -1,int vall= 0):l(ll),r(rr),val(vall){};
    inline bool operator < (const Node &b)const{
        return l<b.l;
    }
};
set<Node> s;//原始的珂朵莉树

构建完了，如果添加元素的话就 s.insert(Node(l,r,val));即可

最核心的操作：Split： 将[l,r]的区间变为[l,pos-1],[pos+1,r]两个区间

inline auto split(int pos){
    auto 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->val;
    s.erase(it);
    s.insert(Node(L,pos-1,v));
    return s.insert(Node(pos,R,v)).first;//这里s.insert返回的是一个pair,first是指向insert之后的节点的。
}

但是如果只有Split，复杂度肯定会炸。所以还有一个操作，用来减少复杂度的：Assign,作用是将[l,l],[l+1,l+1],…,[r,r]合并为一 个区间[l,r]

inline auto assign(int l,int r,int v){//把(l,r)改为v
    auto itL = split(l),itR = split(r+1);
    s.erase(itL,itR);
    s.insert(Node(l,r,v));
}

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

区间加

inline void add(int l,int r,int v){//把(l,r)加上v
    auto itL = split(l),itR = split(r+1);
    for(;itL!=itR;itL++)itL->val+=v;
}

区间第k大(直接取出来排个序)

inline int rnk(int l,int r,int k){
    vector<pair<int,int>> vec;
    auto itL = split(l),itR = split(r+1);
    for(;itL!=itR;itL++)vec.push_back(make_pair(itL->val,itL->r-itL->l+1));
    sort(vec.begin(),vec.end());
    for(auto it = vec.begin();it!=vec.end();it++){
        k-=it->second;
        if(k<=0)return it->first;
    }
    return -1;
}

求和也很奇怪

inline int sum(int l,int r,int ex,int mod){
    auto itL = split(l),itR = split(r+1);
    int res = 0;
    for(;itL!=itR;itL++){
        (res+=Qpow(itL->val,ex,mod)*(itL->r-itL->l+1))%=mod;
    }
    return res;
}

Some Codes

CF896C完整代码:

#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
const int md = 1e9+7;
const int N = 1e5+10;
int n,m,seed,v_max;
int a[N];
int rnd(){
    int ret = seed;
    seed = (seed*7+13)%md;
    return ret;
}
struct Node{
    int l,r;
    mutable int val;
    Node(int ll,int rr = -1,int vall= 0):l(ll),r(rr),val(vall){};
    inline bool operator < (const Node &b)const{
        return l<b.l;
    }
};
set<Node> s;//原始的珂朵莉树
inline int Qpow(int a,int b,int mod){
    int ret = 1;
    a%=mod;
    while(b){
        if(b&1)(ret*=a)%=mod;
        b>>=1;
        (a*=a)%=mod;
    }
    return ret;
}
inline auto split(int pos){
    auto 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->val;
    s.erase(it);
    s.insert(Node(L,pos-1,v));
    return s.insert(Node(pos,R,v)).first;
}
inline auto assign(int l,int r,int v){//把(l,r)改为v
    auto itL = split(l),itR = split(r+1);
    s.erase(itL,itR);
    s.insert(Node(l,r,v));
}
inline void add(int l,int r,int v){//把(l,r)加上v
    auto itL = split(l),itR = split(r+1);
    for(;itL!=itR;itL++)itL->val+=v;
}
inline int rnk(int l,int r,int k){
    vector<pair<int,int>> vec;
    auto itL = split(l),itR = split(r+1);
    for(;itL!=itR;itL++)vec.push_back(make_pair(itL->val,itL->r-itL->l+1));
    sort(vec.begin(),vec.end());
    for(auto it = vec.begin();it!=vec.end();it++){
        k-=it->second;
        if(k<=0)return it->first;
    }
    return -1;
}
inline int sum(int l,int r,int ex,int mod){
    auto itL = split(l),itR = split(r+1);
    int res = 0;
    for(;itL!=itR;itL++){
        (res+=Qpow(itL->val,ex,mod)*(itL->r-itL->l+1))%=mod;
    }
    return res;
}
signed main(){
    cin>>n>>m>>seed>>v_max;
    FOR(i,1,n)s.insert(Node(i,i,rnd()%v_max+1));
    FOR(i,1,m){
        int op = (rnd()%4)+1,l = (rnd()%n)+1,r = (rnd()%n)+1,x,y;
        // cout<<"Op "<<op<<"\n "<<l<<" "<<r<<endl;
        if(l>r)swap(l,r);
        if(op==3)x = rnd()%(r-l+1)+1;
        else x = rnd()%v_max+1;
        if(op==4)y = rnd()%v_max+1;
        if(op==1)add(l,r,x);
        if(op==2)assign(l,r,x);
        if(op==3)cout<<rnk(l,r,x)<<endl;
        if(op==4)cout<<sum(l,r,x,y)<<endl;
        // bl();
    }
}

最后送一个题单，虽然这些题可以用线段树等方法解决，但是学都学了，不用一下不可惜吗

https://www.luogu.com.cn/training/3592

完结★,°:.☆(￣▽￣)/$:.°★ 。

封面来源:

https://wall.alphacoders.com/big.php?i=806829