【算法】The Beautiful Chtholly Tree —B_Z_B_Y

首先 让我们进入珂学的大门 OvO：

珂朵莉树的起源 模板题 QvQ

(ノ≧∇≦)ノ 　珂朵莉　

好了好了，先别欣赏了，看题目首先题意

1、什么是珂朵莉树

珂朵莉树，Chtholly Tree 又称 Old Driver Tree(ODT)（老司机树）。

是一种基于 set 的暴力数据结构。

2、什么时候用珂朵莉树

使一整段区间内的东西变得一样，数据随机。
(这是由于其复杂度和 assign 的操作次数有关，所以当数据随机时会有 $1/4$的概率进行 assign 操作正因为如此复杂度海星）$O(m~log(n)) n,m<=10^5$

3. 初始化

    struct node
    {
        int l,r;
        mutable ll v;//一定要记得 加 mutalbe QAQ
        node(int ls,int rs=-1,ll vv=0) : l(ls),r(rs),v(vv) {}
        bool operator < (const node& ano) const{
            return l < ano.l;
        }
    };//相当于包括了一个三元组表示 [l,r] 区间里有所有数都是 v;
//我们用 set 存储这些三元组，内部维护这些区间，以左端点 L 作为关键字进行升序排列，
//这样方便我们进行一些操作的时候方便查找到我们想要修改的区间。
    set<node> s;
    #define itset set<node> :: iterator 

Chtholly Tree 的本质就是把区间缩成点，set 维护的 Chtholly Tree ，可以视为一棵缩点后的平衡树。需要注意的是 mutable，意为易变的，不定的。它对 v 的修饰，使得我们可以在 add 操作中修改 v 的值。没有它的修饰会在 add 函数里导致 CE

4. 核心操作

操作 split(pos)指将原来含有 pos 位置的节点分成两部分:$[l,pos-1]$和 $[pos,r]$。
由于在 $set$中的所有节点是有序的，我们可以用 $lower\_bound(x)$定位我们要操作的区间。（注: $lower\_bound(x)$可以在 $logn$时间内在一个有序序列中找到最小的 $y$ 使得 $y>=x$

这时我们要分以下两种情况处理通过 $p$ 找到的区间：

1. 如果 $p$ 已经是某个区间的左端点，那么我们直接返回查找到的迭代器;

2. 如果 $p$ 不是某个区间的左端点，那么当前返回的迭代器所指向的区间是 $p$ 所在区间右边第一个区间。这时将迭代器前移一位。如果在前移之后， $p$ 比当前区间的右端点还大，那么直接返回尾迭代器 (因为不需要进行操作)

3. 否则记录一下当前区间的信息，然后直接删除当前区间再插入拆分好的区间 $[L,p-1]$ 和 $[p,R]$ ，最后返回 $p$ 所在区间的迭代器 (操作只会影响包含 $p$ 的区间)。

    itset split(int pos){
        itset it = s.lower_bound(node(pos));

        if(it != s.end() && it->l == pos){
            return it;
        }

        --it;
        if(it->r < pos) return s.end();
        //我不是清楚这个特判到底要不要，因为似乎不加都可以 AC QAQ 求解释
        int ls=it->l , rs=it->r;//[l,r] 就是要分裂的区间
        ll vv=it->v;
        s.erase(it);//删除原节点
        s.insert(node(ls,pos-1,vv));
        return s.insert(node(pos,rs,vv)).first;
        //插入后半段，返回后半段的迭代器。
        //这里利用了 pair<iterator,bool> insert (const value_type& val) 的返回值。
    }

那么接下来 就看看具体的用法

1. 区间赋值

有了 $split$之后，我们就能利用 $split$做各种神 ($ba$o) 奇 ($li$) 的操作了

给一个区间所有的数赋同一个值

首先我们先把 $r+1$ 和 $L$ 所在区间各自拆分出来。既然我们是区间赋值，我们可以直接将 $[L,R)$ 从 set 中移除再添加一个新的 $[L’,R’]$ 区间，其中的值为 $va$l, 而且由于其中有很多小区间被合并在 $[L’,R’]$, 空间复杂度会大大减小

    void assign_v(int l,int r,ll v){
        itset itrs=split(r+1) , itls = split(l);//求出要被摊平区间的收尾地址
        s.erase(itls,itrs);
        s.insert(node(l,r,v));
    }

把 $l$和 $r+1$进行 $split$，再把 $[l,r]$合成一个节点。首先为什么要先 $split$出 $r+$1 呢？因为如果先 $split$出 $l$，再 $split$出 $r+1$，之前的 $itls$可能就不是 $l$对应的迭代器了。QAQ

void erase (iterator first, iterator last)表示可删除 $[first,last)$区间。这里就是把 $[l,r+1)$内的部分推成一段。

2. 区间加法

由于这里 set 的 node 定义我们直接遍历每一集合修改就行了（神 (bao) 奇 (li) 吧 OvO）

    void add(int l,int r,ll val){
        itset itrs = split(r+1) , itls = split(l);
        for(; itls != itrs ; ++itls)
            itls->v += val;
    }

3. 区间 $k$次幂和

和加法很类似 ， 不过要记得乘以区间的大小

    ll sum(int l,int r,int k,int p){
        itset itrs = split(r+1) , itls = split(l);
        ll res = 0 ;
        for(;itls != itrs ; ++itls)//遍历的时候千万不要写错 itls 和 itrs wwwww
            res = (res + (ll) (itls->r - itls->l +1) * (quickpow(itls->v , (ll)k ,(ll)p))) % p;
        return res;
    }

4. 区间第 $k$小

很简单的操作 (但是这玩意可做不能区间第 k 小的模板题啊

第一步依旧是拆分 $r+1$ 与 $L$ 。然后我们将 $[L’, R’)$ 中所有区间拿出来，将区间长度和区间值存到 $pair$，放到 $vector$里，然后对其中所有区间按照 $ v$ 升序排列。然后遍历 $vector$，每次将 $k$ 减去当前区间长度，直到 $ k<=0$ 。十分的神 (bao) 奇 (li)，但是由于数据随机和区间合并时导致区间数量减少，我们依旧能过题

    ll ranks(int l,int r,int k){
        vector<pair<ll ,int > > v;
        //first 放值 ， second 放数量
        itset itrs = split(r+1) , itls = split(l);

        v.clear();

        for(;itls != itrs ; ++itls)
            v.push_back(pair<ll,int> (itls->v , itls->r - itls->l+1));

        sort(v.begin() , v.end());

        for(vector<pair<ll,int> > :: iterator its=v.begin(); its!=v.end(); ++its){

            k -= its->second;
            if(k <= 0)
                return its->first;
        }
        return -1ll;//如果没有，则返回 -1；
    }

最后就上完整代码（注意此题一定要注意精度，CF 题诡异）

#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <set>
using namespace std;

#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(x,i) memset((x),(i),sizeof((x)))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define forvit(i) for(vector<es> :: iterator it=(i).begin();it!=(i).end();++it) 
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#define Tostring(x) #x;
#define Link(x,y) x##y
#define IO(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout);

typedef long  long ll; 
ll read(){
    ll s=0,f=1;
    char c=getchar();
    while(c > '9' || c < '0') {if(c == '-') f=-1;c=getchar();}
    while(c >= '0' && c <= '9') {s=s*10+c-48; c=getchar();}
    return s*f;
}

void write(ll x){
    if(!x) putchar('0');
    if(x < 0) x = -x , putchar('-');

    static int sta[36];
    int tot=0;
    while(x){
        sta[tot++] = x % 10;
        x /= 10;
    }
    while(tot)
        putchar(sta[--tot] + 48);
}

const int maxn = 1e5+7 ;
int n,m;
ll a[maxn];
ll pows(ll a,ll b,ll p){
    ll res=1;
    a %= p;
    while(b){
        if(b & 1) res = (res * a) % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
namespace Chtholly_Tree{
    struct node
    {
        int l,r;
        mutable ll v;
        node(int ls,int rs=-1,ll vv=0) : l(ls),r(rs),v(vv) {}
        bool operator < (const node& ano) const{
            return l < ano.l;
        }
    };
    set<node> s;
    #define itset set<node> :: iterator 

    itset split(int pos){
        itset it = s.lower_bound(node(pos));
        if(it != s.end() && it->l == pos){
            return it;
        }
        --it;
        if(it->r < pos) return s.end();
        int ls=it->l , rs=it->r;
        ll vv=it->v;
        s.erase(it);
        s.insert(node(ls,pos-1,vv));
        return s.insert(node(pos,rs,vv)).first;
    }

    void assign_v(int l,int r,ll v){
        itset itrs=split(r+1) , itls = split(l);
        s.erase(itls,itrs);
        s.insert(node(l,r,v));
    }

    void add(int l,int r,ll val){
        itset itrs = split(r+1) , itls = split(l);
        for(; itls != itrs ; ++itls)
            itls->v += val;
    }
    ll ranks(int l,int r,int k){
        vector<pair<ll ,int > > v;
        itset itrs = split(r+1) , itls = split(l);
        v.clear();
        for(;itls != itrs ; ++itls)
            v.push_back(pair<ll,int> (itls->v , itls->r - itls->l+1));
        sort(v.begin() , v.end());
        for(vector<pair<ll,int> > :: iterator its=v.begin(); its!=v.end(); ++its){
            k -= its->second;
            if(k <= 0)
                return its->first;
        }
    }

    ll sum(int l,int r,int ex,int p){
        itset itrs = split(r+1) , itls = split(l);
        ll res = 0 ;
        for(;itls != itrs ; ++itls)
            res = (res + (ll) (itls->r - itls->l +1) * (pows(itls->v , (ll)ex ,(ll)p))) % p;
        return res;
    }
};
using namespace Chtholly Tree;
const int MOD7 = 1e9 + 7;
ll seed, vmax;//此题诡异的读入方式 以下可以忽略
ll rd()
{
    ll ret = seed;
    seed = (seed * 7 + 13) % MOD7;
    return ret;
}

int main(int argc, char const *argv[])
{
    cin>>n>>m>>seed>>vmax;
    fors(i,1,n){
        a[i] = (rd() % vmax) + 1;
        s.insert(node(i,i,a[i]));
    }
    s.insert(node(n+1,n+1,0));//注意 [l,r) 问题 所以最后在加一个 n+1
    for (int i =1; i <= m; ++i)
    {
        int op = int(rd() % 4) + 1;
        int l = int(rd() % n) + 1;
        int r = int(rd() % n) + 1;
        if (l > r)
            swap(l,r);
        int x, y;
        if (op == 3)
            x = int(rd() % (r-l+1)) + 1;
        else
            x = int(rd() % vmax) +1;
        if (op == 4)
            y = int(rd() % vmax) + 1;
        if (op == 1)
            add(l, r, ll(x));
        else if (op == 2)
            assign_v(l, r, ll(x));
        else if (op == 3)
            cout<<ranks(l,r,x)<<endl;
        else
            cout<<sum(l,r,x,y)<<endl;
    }
    return 0;
}

例题：开始尽情的水题了（Chtholly Tree 30min 解决 QvQ

1. 序列操作 取反要 ^=1

2. 酒店 Hotel (不怎么适合，Chtholly 会 T 一个点 QAQ，所以直接打暴力吧)

3.Physical Education Lessons(在 assign 里直接一下 sum 计数)

4. 区间覆盖 (加强版)

5. 语文 1（chin1）- 理理思维 小范围桶排序，v 设为字符，不要乱强制转化 int)

6. 脑洞治疗仪 (脑洞暴力搞一搞)

最后祝大家 (ノ≧∇≦)ノ NOIP 2018 while(1) ++rp;