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

珂朵莉树的起源 模板题 QvQ

(ノ≧∇≦)ノ  珂朵莉 

s

dsf
sd

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

s

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)的返回值。
    }

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

sd

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;

分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

4 条评论

B_Z_B_Y · 2018年10月22日 8:29 上午

注意一下 namespace Chtholly Tree 应该是 namespace Chtholly_Tree 少了一个下划线 QvQ

    XZYQvQ · 2018年10月22日 12:18 下午

    已经帮您修正了QvQ

litble · 2018年10月19日 7:46 上午

BGM名:Always in my heart

别谢我,我叫珂学家

    XZYQvQ · 2018年10月19日 9:23 上午

    这个暴力吼哇
    QwQ赶紧去玩一波

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *