题解 CF896C 【Willem, Chtholly and Seniorious】
Blaze
2018-11-01 12:01:07
从题目名字可以看出这题要使用一种神奇的数据结构就是**珂朵莉树**!
### 1. 珂朵莉树的原理
**将序列拆成区间来~~暴力~~维护。**
如: $1, 3, 3, 4, 7, 2, 2, 2$
会被拆成(其中一种拆法):
$[1,1]:1,[2,3]:3,[4,4]:4,[5,5]:7,[6,8]:2$
但也有可能会会被拆成(这也正是珂朵莉树会被卡的原因之一):
$[1,1]:1,[2,2]:3,[3,3]:3,[4,4]:4,[5,5]:5,[6,6]:2,[7,7]:2,[8,8]:8$
### 2. 珂朵莉树的适用范围
**题目数据随机且有区间修改操作(如本题)或者对拍(因为好打)~~以及骗分~~。**
### 3. 珂朵莉树的节点
```cpp
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. 珂朵莉树的构造
```cpp
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)**
```cpp
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)**
```cpp
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.珂朵莉树的声明
一维:
```cpp
//重命名
typedef long long value;
typedef chtholly_tree<value> tree;
typedef tree::node node;
typedef tree::it it;
//声明
tree T;
```
二维:
```cpp
//重命名
typedef long long value;
typedef chtholly_tree<chtholly_tree<value> > tree;
//声明
tree T; //跟一维差不多的用法
```
### 7. 珂朵莉树的初始化
```cpp
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. **区间加**
```cpp
//将[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. **区间修改**
```cpp
//将[l,r]区间所有数改成x
void change(int l, int r, value x)
{ T.assign(l, r, x); }
```
调用 **assign** 直接修改
3. **区间第k小**
```cpp
//将[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. **区间幂次和**
```cpp
//快速幂
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}$
2. $m$(平均值)的上界为$(log_\frac{3}{2}4)(log_2n)$~~因为准确界我求不出来~~
由于$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.珂朵莉树的参考程序
```cpp
#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;
}
```