分类导航
程序笔记程序问答

【Coel.做题笔记】【珂艾尔与珂朵莉】Chtholly Tree 珂朵莉树

程序笔记   发布时间：2022-07-01  发布网站：大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了【Coel.做题笔记】【珂艾尔与珂朵莉】Chtholly Tree 珂朵莉树，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题前碎语

我为什么要在期考前写玄学数据结构的笔记…… 我是不是有点大病…… huige说我在越级做题，但是studyingFather的题解里说学会珂朵莉树只要会用std::set（

题目简介

CF896C Willem, Chtholly and Seniorious CodeForces原题传送门 洛谷传送门 题目背景就不抄了，想看的珂学家可以直接去看原题。

@H_618_10@题目描述

实现一个支持以下操作的数据结构：

  • (1) (l) (r) (X) ：将([l,r]) 区间所有数加上(X)
  • (2) (l) (r) (X) ：将([l,r]) 区间所有数改成(X)
  • (3) (l) (r) (X) ：输出将([l,r]) 区间从小到大排序后的第(X) 个数是的多少(即区间第(X) 小，数字大小相同算多次，保证 (1leq) (X) (leq) (r-l+1) )
  • (4) (l) (r) (X) (y) ：输出([l,r]) 区间每个数字的(X) 次方的和模(y) 的值(即((sum^r_{i=l}a_i^X) ) (mod y) )
@H_618_10@输入格式

这道题目的输入格式比较特殊，需要选手通过(seed) 自己生成输入数据。 输入一行四个整数(n,m,seed,v_{max}) （(1leq) (n,mleq 10^{5}) ,(0leq seed leq 10^{9}+7) (,1leq vmax leq 10^{9}) ） 其中(n) 表示数列长度，(m) 表示操作次数，后面两个用于生成输入数据。 题目给出用于生成数据的伪代码如下：

def rnd():

    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:

    a[i] = (rnd() mod vmaX) + 1

for i = 1 to m:

    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1

    if (l > r): 
         swap(l, r)

    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmaX) + 1

    if (op == 4):
        y = (rnd() mod vmaX) + 1
@H_618_10@输出格式

对于每个操作3和4，输出一行仅一个数。

这题需要实现的就是大名鼎鼎的珂朵莉树——(Chtholly) (TreE)(又叫(Old)-(Driver) (TreE),简称(ODT))。 不过根据各位大佬的解释，珂朵莉树实际上不能算是一种数据结构，而是一种暴力解决问题的算法技巧。

不管这么多，直接开始正题。 珂朵莉树最出众的功能就是推倒（hso）操作，把一个区间全部修改为同一个数，也就是这题的操作2。 当然，我们首先得写一个结构体，把每个区间的左端点、右端点和数值存起来。

struct odt {
    ll left, right;
    mutable ll val;
 
    odt(ll left, ll right = 0, ll val = 0) : left(left), right(right), val(val) {}//初始化，当然强制转换也行
 
    inline bool operator<(const odt &X) const {
        return left < x.left;//按左端点排序
    }
};

注意到对val的定义多了个@H_592_7@mutable关键字，这个在之后的操作里有很大作用，暂且卖个关子。 接下来用一个set把点给存起来进行初始化。伪代码中给出的数据用a[i]表示，这里直接插进set里就好了，不需要这个数组。

std::set< odt > S;
for (int i = 1; i <= n; i++)
        s.insert(odt(i, i, (rnd() % vmaX) + 1));

很快，我们来到了珂朵莉树最为核心最为关键的一个函数：(split)! （它是如此关键以至于我要用一个(LaTeX)来强调） 这个函数的作用是把一个区间分割成([left,pos-1])和([pos,right])，这样才方便之后的合并；同时返回一个迭代器，代表后半段开头。 先定义一个迭代器表示不小于pos的点，然后分成以下几个情况看待：

  • 如果这个区间以pos为起点，那就不需要做任何事，直接返回这个迭代器；
  • 如果右端点比pos还要小，那就直接返回s.end()；
  • 如果把Pos包含上了，才需要把区间分成两半，顺便把原来那个区间删掉。
auto split(ll pos) {
    auto it = s.lower_bound(odt(pos));
 
    if (it != s.end() && (it -> left) == pos)//情况1
        return it;
 
    it--;
 
    if ((it -> right) < pos)//情况2
        return s.end();
 
    ll l = it -> left, r = it -> right, v = it -> val;//情况3
 
    s.erase(it);
    s.insert(odt(l, pos - 1, v));
 
    return s.insert(odt(pos, r, v)).first;
}

这里利用到了两个小技巧。 第一个是insert函数有返回值，是一个pair，并且这个pair的first就是我们需要的后半段开头的迭代器，所以直接返回。 第二个就是C++14的独门秘技——auto！！！ auto可以直接根据数据判定数据类型，这是一个很棒的东西。 试想一下，如果没有auto，写一个迭代器定义就只能是： std::set< odt >::iterator 写起来又累又容易打错！ 虽然我们可以用宏定义解决这个问题，但是auto就能轻松解决。 有人可能会问了：

auto不是C++11就有了吗？

确实，但是在C++11，auto不能作为函数返回值，这意味着我们的(split)只能回到那个冗长的样子。 更重要的是，在NOI-Linux 2.0里，C++14统一使用！！！ 改革春风吹满地，用C++14的CCF真神气！ 啊好像有点跑题了（

下一个要实现的就是推倒区间的操作——assign。 有了前面split的铺垫，这一步就灰常简单了~ 定义两个迭代器代表区间左端点和右端点，用split把区间分解，然后插入推倒之后的新区间，并且用s.erase(it_l, it_r)删掉之前的区间。 需要注意的是，一定要先分解后半段再分解前半段，否则会访问到空区间导致RE。

void assign(ll l, ll r, ll v) {
    auto it_r = split(r + 1), it_l = split(l);
    s.erase(it_l, it_r);
    s.insert(odt(l, r, v));
}

剩下的几个操作也都很简单，快点过掉吧~

全部加上一个数： 定义端点-遍历-直接加，简单粗暴。

void add(ll l, ll r, ll v) {
    auto it_r = split(r + 1), it_l = split(l);
    for (auto it = it_l; it != it_r; it++)
        it->val += v;
}

前面提到的multable就是在这儿发挥作用的~ iterator是常量迭代器，正常情况下没法改数据，但是加上了multable就意味着常量也可以被强制修改，加数字就能轻松实现了~

查询区间第x小： 全部扔到一个vector里面排序，然后逐个相减，也很简单粗暴。 有的题解又定义一个结构体，其实用pair足矣：first代表数字，second代表相同数字的数量（有点像桶排序里的桶？）。 顺带一提，这个函数我一开始犯了各种各样的低级错误，还被huige说了一顿……qwq

ll rank(ll l, ll r, ll X) {
    std::vector< std::pair<ll, ll> > V;
    auto it_r = split(r + 1), it_l = split(l);
 
    for (auto it = it_l; it != it_r; it++)
        V.push_BACk(std::make_pair(it -> val, (it -> right) - (it -> left) + 1));
    
    std::sort(V.begin(), V.end());
 
    auto it = V.begin();
 
    while (it != V.end() && it -> second < X)
        x -= (it -> second),it++;
    return it -> first;
}

不知道在干什么的申必操作求乘方和取模，同样很暴力。 小提醒：做快速幂的时候要先把底数模一下，因为有可能在a*a%p的时候爆long long导致结果错误。

ll calc(ll l, ll r, ll x, ll y) {
    auto it_r = split(r + 1), it_l = split(l);
    ll ans = 0;
 
    for (auto it = it_l; it != it_r; ++it) 
        ans = (ans + qpow(it -> val, x, y) * ((it -> right) - (it -> left) + 1) % y) % y;
    
    return ans;
}

好啦，所有操作实现完成，是时候祭出珂朵莉树的完整代码了！

#include <set>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
 
typedef long long ll;
 
const ll mod = 1000000007;
 
ll n, m, seed, vmax;
 
struct odt {
    ll left, right;
    mutable ll val;
 
    odt(ll left, ll right = 0, ll val = 0) : left(left), right(right), val(val) {}
 
    inline bool operator<(const odt &X) const {
        return left < x.left;
    }
};
 
std::set< odt > S;
 
inline ll qpow(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;

    while (b) {
        if (b % 2 == 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
 
    return ans;
}
 
auto split(ll pos) {
    auto it = s.lower_bound(odt(pos));
 
    if (it != s.end() && it -> left == pos)
        return it;
 
    it--;
 
    if (it -> right < pos)
        return s.end();
 
    ll l = it -> left, r = it -> right, v = it -> val;
 
    s.erase(it);
    s.insert(odt(l, pos - 1, v));
 
    return s.insert(odt(pos, r, v)).first;
}
 
void assign(ll l, ll r, ll v) {
    auto it_r = split(r + 1), it_l = split(l);
    s.erase(it_l, it_r);
    s.insert(odt(l, r, v));
}
 
void add(ll l, ll r, ll v) {
    auto it_r = split(r + 1), it_l = split(l);
    for (auto it = it_l; it != it_r; it++)
        it->val += v;
}
 
ll rank(ll l, ll r, ll X) {
    std::vector< std::pair<ll, ll> > V;
    auto it_r = split(r + 1), it_l = split(l);
 
    for (auto it = it_l; it != it_r; it++)
        V.push_BACk(std::make_pair(it -> val, (it -> right) - (it -> left) + 1));
    
    std::sort(V.begin(), V.end());
 
    auto it = V.begin();
 
    while (it != V.end() && it -> second < X)
        x -= (it -> second),it++;
    return it -> first;
    return -1;
}
 
ll calc(ll l, ll r, ll x, ll y) {
    auto it_r = split(r + 1), it_l = split(l);
    ll ans = 0;
 
    for (auto it = it_l; it != it_r; ++it) 
        ans = (ans + qpow(it -> val, x, y) * (it -> right - it -> left + 1) % y) % y;
    
    return ans;
}
 
inline ll rnd() {
    ll ans = seed;
    seed = (seed * 7 + 13) % mod;
    return ans;
}
 
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmaX);
 
    for (int i = 1; i <= n; i++)
        s.insert(odt(i, i, (rnd() % vmaX) + 1));
 
    for(int i = 1; i <= m; i++) {
        ll op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, y;
 
        if (l > r)
            std::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 : add(l, r, X); break;
            case 2 : assign(l, r, X); break;
            case 3 : printf("%lldn", rank(l, r, X)); break;
            case 4 : printf("%lldn", calc(l, r, x, y)); break;
        }
    }
 
    return 0;
}

题后闲话

写完还要被老妈催去睡觉，烦耶…… 过几天就要期考了，祝自己期考顺利ww

大佬总结

以上是大佬教程为你收集整理的【Coel.做题笔记】【珂艾尔与珂朵莉】Chtholly Tree 珂朵莉树全部内容，希望文章能够帮你解决【Coel.做题笔记】【珂艾尔与珂朵莉】Chtholly Tree 珂朵莉树所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：c++linuxphpwhile排序程序员算法遍历
猜你在找的程序笔记相关文章
其他相关热搜词更多
phpJavaPython程序员load中如何string使用参数jquery开发安装listlinuxiosandroid工具javascriptcap