题解 CF896C 【Willem, Chtholly and Seniorious】

Blaze · 2018-11-01 12:01:07 · 题解

从题目名字可以看出这题要使用一种神奇的数据结构就是珂朵莉树！

1. 珂朵莉树的原理

将序列拆成区间来暴力维护。

如: 1, 3, 3, 4, 7, 2, 2, 2

会被拆成(其中一种拆法)：

但也有可能会会被拆成(这也正是珂朵莉树会被卡的原因之一)：

2. 珂朵莉树的适用范围

题目数据随机且有区间修改操作(如本题)或者对拍(因为好打)以及骗分。

3. 珂朵莉树的节点

template<typename _Tp> //要维护信息的类型
struct chtholly_node   //珂朵莉树的节点
{
  typedef _Tp value;   //重命名_Tp为value
  mutable int l, r;    //要维护的区间[l, r]
  mutable value v;     //整个区间[l, r]上序列所共有的值
  chtholly_node(int L, int R, value x) : l(L), r(R), v(x) { };
  bool operator<(const chtholly_node &x) const
  { return l < x.l; }  //按左端点从小到大排序
};

每个节点维护一段区间[l,r]及其上的值v(注意区间不能相交)。(注：下面不再区分节点和区间，即区间有可能是节点，节点也有可能是区间，需结合自己理解。)

4. 珂朵莉树的构造

template<typename _Tp> //要维护信息的类型
struct chtholly_tree : public set<chtholly_node<_Tp> >
{
  //重命名
  typedef _Tp value;
  typedef chtholly_node<value> node;
  typedef typename set<chtholly_node<value> >::iterator it;
  //操作
  it split(int pos);
  void assign(int l, int r, value x);
};

珂朵莉树继承了set,使得可以像使用set一样使用它，并重命名了一些冗长的数据类型，以及附加了两个新操作。

5. 珂朵莉树的操作

1. it split(int pos)

 template<typename _Tp>
 typename chtholly_tree<_Tp>::it chtholly_tree<_Tp>::split(int pos)
 {
     it itl = this->lower_bound(node(pos, -1, value()));
     if(itl != this->end() && itl->l == pos) return itl; --itl;
     it itr = this->insert(node(pos, itl->r, itl->v)).first; itl->r = pos - 1;
     return itr;
 }

作用：将pos所在的区间[l,r]分成[l,pos-1]和[pos,r]并返回[pos,r]所在的迭代器(若pos = l则返回[l,r]所在的迭代器)。

内容：首先 lower_bound(node(pos, -1, value()) 返回左端点大于等于pos且最小的区间所在的迭代器并赋给迭代器itl，然后判断itl所指区间的左端点是否等于pos，如果是的就直接返回itl即区间[l,r]所在的迭代器，否则就跳到上一个迭代器(即左端点小于pos且最大的区间所在的迭代器)，接着 insert(node(pos, itl->r, itl->v)).first 会复制区间[l,r]上的[pos,r]并插入且返回[pos,r]所在的迭代器赋给itr，此时只需将itl所指的区间[l,r]改为[l,pos-1]即将r改为pos-1即可，最后返回itr即[pos,r]所在的区间。

2. void assign(int l, int r, value x)

 template<typename _Tp>
 void chtholly_tree<_Tp>::assign(int l, int r, value x)
 {
     it itl = this->split(l), itr = this->split(r + 1);
     this->erase(itl, itr); this->insert(node(l, r, x));
 }

作用：将区间[l,r]上的序列所共有的值修改为x。

内容：首先 split(l) 返回一个以l为左端点的区间的迭代器赋给itl, split(r + 1) 返回一个以r + 1为左端点的区间的迭代器赋给itr, 然后 erase(itl, itr) 会删除所有左端点在区间[l,r + 1)即[l,r]的区间即删除区间[l,r]上的整个序列， 接着 insert(node(l, r, x)) 会插入一个序列所共有的值为x的区间[l,r]。

注意：请确保调用 split 和 assign 时 chtholly_tree 不为空。

6.珂朵莉树的声明

一维：

//重命名
typedef long long value;
typedef chtholly_tree<value> tree;
typedef tree::node node;
typedef tree::it it;
//声明
tree T;

二维：

//重命名
typedef long long value;
typedef chtholly_tree<chtholly_tree<value> > tree;
//声明
tree T; //跟一维差不多的用法

7. 珂朵莉树的初始化

for(int i = 1; i <= n; i++)
  T.insert(node(i, i, rnd() % vmax + 1));

注：如果一开始序列是空的那么就 T.insert(l, r, v) 其中[l,r]为全域大小，v为一个空值，如 T.insert(0, (int)1e9, 0) 。

8. 珂朵莉树的暴力维护

1. 区间加

 //将[l,r]区间所有数加上x
 void add(int l, int r, value x)
 {
     it itl = T.split(l), itr = T.split(r + 1);
     for(; itl != itr; ++itl) itl->v += x;
 }

直接将左端点在[l,r)的区间中最左边的区间依次加到最右边的区间。

2. 区间修改

 //将[l,r]区间所有数改成x
 void change(int l, int r, value x)
 { T.assign(l, r, x); }

调用 assign 直接修改

3. 区间第k小

 //将[l,r]区间从小到大排序后的第x个数是的多少
 value select(int l, int r, value x)
 {
     it itl = T.split(l), itr = T.split(r + 1);
     vector<pair<value, int> > vp;
     for (; itl != itr; ++itl)
       vp.push_back(pair<value,int>(itl->v, itl->r - itl->l + 1));
      std::sort(vp.begin(), vp.end());
     for(vector<pair<value,int> >::iterator it = vp.begin(); it != vp.end(); ++it)
       if((x -= it->second) <= 0)
         return it->first;
     return -1;
 }

将左端点在[l,r)的区间中最左边的区间到最右边的区间依次复制到 vector 里，排序，顺次找到第k小(注意：vector 里保存的是区间)。

4. 区间幂次和

 //快速幂
 value pow(value x, value y, value m)
 {
     value res = 1, ans = x % m;
     while(y)
     {
       if(y & 1) res = res * ans % m;
       ans = ans * ans % m;
       y >>= 1;
     }
     return res;
 }
 //返回[l,r]区间每个数字的x次方的和模y的值
 value sum(int l, int r, value x, value y)
 {
     it itl = T.split(l), itr = T.split(r + 1);
     value res = 0;
     for(; itl != itr; ++itl)
       res = (res + (itl->r - itl->l + 1) * pow(itl->v, x, y)) % y;
     return res;
 }

将左端点在[l,r)的区间中最左边的区间到最右边的区间依次快速幂累加即可。

9. 珂朵莉树的时间复杂度

记 m为区间数即T.size()。

1. 对于随机的l和r其区间[l,r]的平均长度为\frac{n-1}{3}

证明：\overline{x} = \frac{\sum_{l=1}^{n}\sum_{r=l}^{n}(r-l)}{\sum_{l=1}^{n}\sum_{r=l}^{n}1}=\frac{\frac{1}{2}\sum_{l=1}^{n}(\sum_{l=1}^{n}l^2-(2n+1)\sum_{l=1}^{n}l+n^3+n^2)}{\frac{1}{2}n(n+1)} =\frac{\frac{2}{3}n(n+1)(n-1)}{\frac{1}{2}n(n+1)}=\frac{n-1}{3}

由于m与n对应，每次 assign 均会使得m变为\frac{2}{3}m+\frac{2}{3}且有概率在l及r上分裂出两个新区间，又因为只需求出m(平均值)的上界于是我们可以使得每次 assign 均会使得m变为\frac{2}{3}m，且永久地增加两个区间，可知进行k次操作后m变为(\frac{2}{3})^km有1=(\frac{2}{3})^km即k=log_\frac{3}{2}m，于是最终会有2k即2log_\frac{3}{2}m个区间，由初始条件m=n得出在进行足够多的 assign 情况下m(平均值)的上界为2log_\frac{3}{2}n即(log_\frac{3}{2}4)(log_2n)。(经过测试m的收敛速度远没有上述那么快(n=1e8时大约要1e6次 assign 操作m(平均值)才会基本上不会变动)，另外m(平均值)的值大约在\frac{3}{2}log_2n左右)。

3. split 的均摊时间复杂度为O(log_2log_2n)

由 split 的时间复杂度为O(log_2m)可知 split 的均摊时间复杂度为O(log_2log_2n)。

4. assign 的均摊时间复杂度为O(log_2log_2n)

由 assign 的时间复杂度为O(log_2m)可知 assign 的均摊时间复杂度为O(log_2log_2n)。

5. add 的均摊时间复杂度为O(log_2n)

由 add 的时间复杂度为O(m)可知 add 的均摊时间复杂度为O(log_2n)。

6. change 的均摊时间复杂度为O(log_2log_2n)

由 change 的时间复杂度为O(log_2m)可知 change 的均摊时间复杂度为O(log_2log_2n)。

7. select 的均摊时间复杂度为O((log_2n)(log_2log_2n))

由 select 的时间复杂度为O(mlog_2m)可知 select 的均摊时间复杂度为O((log_2n)(log_2log_2n))。

8. sum 的均摊时间复杂度为O(log_2n)

由 pow 的时间复杂度为O(1)(全域为[1,1e9])，

及 sum 的时间复杂度为O(m)可知 sum 的均摊时间复杂度为O(log_2n)。

从此可以看出珂朵莉树的时间复杂度完全是由随机的 assign 操作保证的，这也就导致了珂朵莉树的适用范围狭小。

10.珂朵莉树的参考程序

#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
using namespace std;

//珂朵莉树的节点
template<typename _Tp>
struct chtholly_node
{
  typedef _Tp value;
  mutable int l, r;
  mutable value v;
  chtholly_node(int L, int R, value x) : l(L), r(R), v(x) { }
  bool operator<(const chtholly_node& x) const { return l < x.l; }
};

//珂朵莉树的构造
template<typename _Tp>
struct chtholly_tree : public set<chtholly_node<_Tp> >
{
  typedef _Tp value;
  typedef chtholly_node<value> node;
  typedef typename set<chtholly_node<value> >::iterator it;

  //珂朵莉树的操作
  it split(int pos)
  {
    it itl = this->lower_bound(node(pos, -1, value()));
    if(itl != this->end() && itl->l == pos) return itl; --itl;
    it itr = this->insert(node(pos, itl->r, itl->v)).first; itl->r = pos - 1;
    return itr;
  }
  void assign(int l, int r, value x)
  {
    it itl = this->split(l), itr = this->split(r + 1);
    this->erase(itl, itr); this->insert(node(l, r, x));
  }
};

//珂朵莉树的声明
typedef long long value;
typedef chtholly_tree<value> tree; typedef tree::node node; typedef tree::it it;
tree T;

//珂朵莉树的维护
void add(int l, int r, value x)
{
  it itl = T.split(l), itr = T.split(r + 1);
  for(; itl != itr; ++itl) itl->v += x;
}
void change(int l, int r, value x)
{ T.assign(l, r, x); }
value select(int l, int r, value x)
{
  it itl = T.split(l), itr = T.split(r + 1);
  vector<pair<value, int> > vp;
  for (; itl != itr; ++itl)
    vp.push_back(pair<value, int>(itl->v, itl->r - itl->l + 1));
  std::sort(vp.begin(), vp.end());
  for(vector<pair<value, int> >::iterator it = vp.begin(); it != vp.end(); ++it)
    if((x -= it->second) <= 0)
      return it->first;
  return -1;
}
value pow(value x, value y, value m)
{
  value res = 1, ans = x % m;
  while(y)
  {
    if(y & 1) res = res * ans % m;
    ans = ans * ans % m;
    y >>= 1;
  }
  return res;
}
value sum(int l, int r, value x, value y)
{
  it itl = T.split(l), itr = T.split(r + 1);
  value res = 0;
  for(; itl != itr; ++itl)
    res = (res + (itl->r - itl->l + 1) * pow(itl->v, x, y)) % y;
  return res;
}

value n, m, seed, vmax;
value rnd()
{ value ret = seed; seed = (seed * 7 + 13) % 1000000007; return ret; }

int main(int argc, char* argv[])
{
  cin >> n >> m >> seed >> vmax;
  value op, l, r, x, y;

  //珂朵莉树的初始化
  for(int i = 1; i <= n; i++) T.insert(node(i, i, rnd() % vmax + 1));

  for(int i = 1; i <= m; i++)
  {
    op = rnd() % 4 + 1; l = rnd() % n + 1; r = rnd() % n + 1;
    if(l > r) 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:
      change(l, r, x);
      break;
    case 3:
      cout << select(l, r, x) << endl;
      break;
    case 4:
      cout << sum(l, r, x, y) << endl;
      break;
    }
  }
  return 0;
}