题解 CF896C 【Willem, Chtholly and Seniorious】

从题目名字可以看出这题要使用一种神奇的数据结构就是**珂朵莉树**！ ### 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; } ```