这道题根据给的图片能明显看出是一道珂朵莉树

经典的珂朵莉树例题！

名称简介

老司机树，ODT（Old Driver Tree），又名珂朵莉树（ Chtholly Tree ）。起源自 CF896C （本题）。

前置的必会知识

由于使用到 STL 的集合，需要你会使用 set。

核心思想

把值相同的区间合并成一个结点保存在 set 里面。 类似于 lazytag。

用处

高情商：暴力，低情商：骗分。

只要是有区间赋值操作的数据结构题都可以用来骗分。在数据随机的情况下一般效率较高，但在不保证数据随机的场合下，会被精心构造的特殊数据卡到超时。

如果要保证复杂度正确，必须保证数据随机。详见 CF(Codeforces) 上关于珂朵莉树的时间复杂度的证明.

更详细的严格证明见 珂朵莉树的复杂度分析。对于 add, assign 和 sum 操作，用 set 实现的珂朵莉树的复杂度为 O(n \log \log n) ，而用链表实现的复杂度为 O(n \log n).

正文

首先，对于每一个区间，我们一般定义一个节点结构体：

struct Node
{
    int l,r;
    mutable int v;
    Node(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}//构造函数
    inline bool operator<(const Node &o) const { return l < o.l; }
};

mutable 关键字的作用是什么？

mutable 是一个英语单词。他的中文意思是可变的，由于 set 本身不可以修改值，我们加上 mutable 关键字后让我们可以修改这个值。在 C++ 中，mutable 的存在其实是为了突破 const 的限制而设置的。被 mutable 修饰的变量（mutable 只能用于修饰类中的非静态数据成员），将永远处于可变的状态，即使在一个 const 函数中。

在这之后，我们有了节点结构体了，我们定义一个集合存储并维护这些节点。

set<Node> ct;//Chtholly Tree

为了简化下面的代码，我们typedef一个it类型：

typedef set<Node>::iterator it;

其中 iterator 是迭代器的意思。当然了，如果题目像本题一样支持 C++11，使用 auto 也是可以的。

iterator(迭代器)小知识

在 STL 中，迭代器（Iterator）用来访问和检查 STL 容器中元素的对象，它的行为模式和指针类似，但是它封装了一些有效性检查，并且提供了统一的访问格式.类似的概念在其他很多高级语言中都存在，如 Python 的 __iter__ 函数，C# 的 IEnumerator。

split

split 是最核心的操作之一，它用于将原本包含点 x 的区间（ 先将其设为 [l,r] ）分裂为两个区间 [l,x) 和 [x,r] 并返回指向后者的迭代器。参考代码如下：

it split(int x) 
{
  if (x > n) return ct.end();
  it iter = --ct.upper_bound((Node){x, 0, 0});
  if (iter->l == x) return iter;
  int l = iter->l, r = iter->r, v = iter->v;
  ct.erase(iter);
  ct.insert(Node(l, x - 1, v));
  return ct.insert(Node(x, r, v)).first;
}

那么 split 函数的具体作用是什么呢？ 任何对于 [l,r] 的区间操作，都可以转换成 set 上 [split(l),split(r+1)] 的操作。

assign

刚才提到了区间赋值，这就是 assign 函数的作用。 对于 ODT 来说，区间操作只有这个比较特殊，也是保证复杂度的关键。如果 ODT 里全是长度为 1 的区间，就成了暴力，但是有了 assign，可以使 ODT 的大小下降。参考代码如下：

void assign(int l, int r, int v) 
{
  it itr = split(r + 1), itl = split(l);
  ct.erase(itl, itr);
  ct.insert(Node(l, r, v));
}

其他操作

一般更改以下模板就好啦！参考模板代码如下：

void performance(int l, int r) 
{
  it itr = split(r + 1), itl = split(l);
  for (; itl != itr; ++itl) 
  {
    // Puts your code here!
    //这个循环迭代 [split(l),split(r+1)] 中的每一个元素
  }
}

注：珂朵莉树在进行求取区间左右端点操作时，必须先 split 右端点，再 split 左端点。若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，可能会导致 RE。

对于本题的其他操作

1.区间+

直接改模板就好啦！参考代码如下所示：

void add(int l, int r,int v) 
{
  it itr = split(r + 1), itl = split(l);
  for (; itl != itr; ++itl) 
  {
    itl->v += v;//由于我们的v声明时使用了mutable关键字，直接更改即可
  }
}

2.区间第k小

这个我们可以先定义一个 vector 动态数组存储区间 [l,r] 的每一个元素， 之后直接对这个 vector 数组排序，然后访问第k小元素即可。对于 vector 存储的类型，我们可以存 pair，first 存值，second 存这个元素在珂朵莉树里的位置，刚好可以使用 STL 的 sort 函数（算法头文件有定义 pair 的小于号,比较 first 元素的大小 ）。 参考代码如下：

inline int kth(int l,int r,int k)
{
   vector< pair<int,int> > a;
   it itr=split(r+1),itl=split(l);
   for(it iter=itl;iter!=itr;iter++)
      a.push_back(pair<int,int>(iter->v,(iter->r)-(iter->l)+1));//使用pair的构造函数
   sort(a.begin(),a.end());
   for(vector< pair<int,int> >::iterator iter=a.begin();iter!=a.end();iter++)
   {
      k-=iter->second;
      if(k<=0)return iter->first;
   }
   return -1;
}

3.区间次幂和

同样还是暴力，不过比区间第k小相对简单，我们直接取出每个值之后相加就可以。 参考代码如下：

long long fpow(long long x,long long y,long long mod)
{
    long long ans=1;
    x%=mod;
    while(y) //快速幂
    {
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
int sum(int l,int r,int x,int y)
{
   int ans=0;
   it itr=split(r+1),itl=split(l);
   for(it it=itl;it!=itr;it++)
      ans=(ans+fpow(it->v,x,y)*((it->r)-(it->l)+1))%y;//注意使用fpow函数，这个函数是我们自己定义的快速幂。
   return ans;
}

注意事项

我们的区间操作都是直接对值相同的连续段进行处理，当段数较多的时候，效率就会降低。

参考代码

#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define int long long 
struct Node
{
    int l,r;
    mutable int v;
    Node(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}//构造函数
    inline bool operator<(const Node &o) const { return l < o.l; }
};
set<Node> ct;//Chtholly Tree
#define S ct
long long n, m, seed, vmax;
typedef set<Node>::iterator it;
it split(int x)
{
    if (x > n) return ct.end();
    it iter = --ct.upper_bound((Node){x, 0, 0});
    if (iter->l == x) return iter;
    int l = iter->l, r = iter->r, v = iter->v;
    ct.erase(iter);
    ct.insert(Node(l, x - 1, v));
    return ct.insert(Node(x, r, v)).first;
}
void assign(int l, int r, int v) 
{
    it itr = split(r + 1), itl = split(l);
    ct.erase(itl, itr);
    ct.insert(Node(l, r, v));
}
void add(int l, int r,int v) 
{
    it itr = split(r + 1), itl = split(l);
    for (; itl != itr; ++itl) 
    {
        itl->v += v;//由于我们的v声明时使用了mutable关键字，直接更改即可
    }
}
inline int kth(int l,int r,int k)
{
    vector< pair<int,int> > a;
    it itr=split(r+1),itl=split(l);
    for(it iter=itl;iter!=itr;iter++)
        a.push_back(pair<int,int>(iter->v,(iter->r)-(iter->l)+1));//使用pair的构造函数
    sort(a.begin(),a.end());
    for(vector< pair<int,int> >::iterator iter=a.begin();iter!=a.end();iter++)
    {
        k-=iter->second;
        if(k<=0)return iter->first;
    }
    return -1;
}
long long fpow(long long x,long long y,long long mod)
{
    long long ans=1;
    x%=mod;
    while(y) //快速幂
    {
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
int sum(int l,int r,int x,int y)
{
    int ans=0;
    it itr=split(r+1),itl=split(l);
    for(it it=itl;it!=itr;it++)
        ans=(ans+fpow(it->v,x,y)*((it->r)-(it->l)+1))%y;//注意使用fpow函数，这个函数是我们自己定义的快速幂。
    return ans;
}

long long a[100010];
inline long long rnd() 
{
    long long ret = seed;
    seed = (seed * 7LL + 13) % 1000000007LL;
    return ret;
}
signed main()
{
    ct.clear();
    cin>>n>>m>>seed>>vmax;
    for(int i = 1; i <= n; ++i)
    {
        a[i] = (rnd()%vmax) + 1;
        S.insert(Node(i, i, a[i]));
    }
    S.insert(Node(n+1,n+1,0));
    for(int i = 1; i <= m; ++i)
    {
        long long op = rnd()%4 + 1;
        long long l = rnd() % n + 1, r = rnd() % n + 1;
        if(l > r)
        {
            long long tmp = l;
            l = r;
            r = tmp;
        }
        long long x, y;
        if(op == 3)
        {
            x = rnd() % (r - l + 1) + 1;
        }
        else
        {
            x = rnd() % vmax + 1;
        }
        if(op == 4)
        {
            y = rnd() % vmax + 1;
        }
        if(op == 1)  add(l, r, x);
        else if(op == 2)  assign(l, r, x);
        else if(op == 3)  printf("%lld\n", kth(l, r, x));
        else if(op == 4)  printf("%lld\n", sum(l, r, x, y));
    }
    return 0;
}

写在最后

以上就是关于本道 ODT/珂朵莉树 模板题题解的全部内容啦！祝你能够通过自己的能力通过本题，不要抄袭。

新人第一次写题解，若有不足请见谅。