题解 CF896C 【Willem, Chtholly and Seniorious】

珂朵莉树模板题。 ## 一、什么是珂朵莉树 珂朵莉树，又称Old Driver Tree(ODT)。是一种基于```std::set```的暴力数据结构。B站上有UESTC的[讲解视频](https://www.bilibili.com/video/av21651173)。 ## 二、什么时候用珂朵莉树 关键操作：推平一段区间，使一整段区间内的东西变得一样。保证数据随机。 就像这道题。 $n$个数，$m$次操作$(n,m\leq10^5)$。 操作： 1. 区间加 2. **区间赋值** 3. 区间第k小 4. 求区间幂次和 **数据随机**，时限2s。 ## 三、珂朵莉树的初始化 这道题里，这样定义珂朵莉树的节点： ``` struct node { int l,r; mutable LL v; node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {} bool operator<(const node& o) const { return l < o.l; } }; ``` 这样的一个节点表示$[l,r]$内的所有数都是v。需要注意的是```mutable```，意为易变的，不定的。它对```v```的修饰，使得我们可以在```add```操作中修改```v```的值。没有它的修饰会在```add```函数里导致CE。 我们把节点存在```set```里。 ``` set<node> s; ``` 像CF896C这道题就这样初始化。 ``` cin>>n>>m>>seed>>vmax; for (int i=1; i<=n; ++i) { a[i] = (rnd() % vmax) + 1; s.insert(node(i,i,a[i])); } ``` 初始化完了？初始化完了。 ## 四、珂朵莉树的核心操作：split ```split(pos)```操作是指将原来含有pos位置的节点分成两部分：$[l,pos-1]$和$[pos,r]$。 看这个操作的代码： ``` #define IT set<node>::iterator IT split(int pos) { IT it = s.lower_bound(node(pos)); if (it != s.end() && it->l == pos) return it; --it; int L = it->l, R = it->r; LL V = it->v; s.erase(it); s.insert(node(L, pos-1, V)); return s.insert(node(pos, R, V)).first; } ``` 一行一行来看。 ``` #define IT set<node>::iterator ``` 宏定义没什么好说的，记住NOI系列赛事不能用```auto```。```auto```一时爽，评测火葬场。 ``` IT it = s.lower_bound(node(pos)); ``` 找到首个$l$不小于pos的节点。 ``` if (it != s.end() && it->l == pos) return it; ``` 如果无需```split```，直接返回。 ``` --it; ``` 否则pos一定在前一个区间中。 ``` int L = it->l, R = it->r; ``` $[L,R]$就是要被分割的区间。 ``` LL V = it->v; ``` 取出这个节点的值。 ``` s.erase(it); ``` 删除原节点。 ``` s.insert(node(L, pos-1, V)); ``` 插入前半段。 ``` return s.insert(node(pos, R, V)).first; ``` 插入后半段，返回后半段的迭代器。这里利用了```pair<iterator,bool> insert (const value_type& val)```的返回值。 ## 五、珂朵莉树的推平操作：assign 要是只有```split```还不得复杂度爆炸？我们需要```assign```操作迅速减小```set```的规模。 ``` void assign(int l, int r, LL val=0) { IT itl = split(l),itr = split(r+1); s.erase(itl, itr); s.insert(node(l, r, val)); } ``` 一些萌新可能没有见过```erase```的这种用法，你们应该学习一个。C++98中```void erase (iterator first, iterator last)```可删除$[first,last)$区间。这里就是把$[l,r+1)$内的部分推成一段。 珂朵莉树的复杂度是由```ass```♂```ign```保证的。由于数据随机，有$\frac{1}{4}$的操作为```assign```。```set```的大小快速下降，最终趋于$\log n$，使得这种看似暴力无比的数据结构复杂度接近$m\log n$。 ## 六、其他操作：一个比一个暴力 区间加： ``` void add(int l, int r, LL val=1) { IT itl = split(l),itr = split(r+1); for (; itl != itr; ++itl) itl->v += val; } ``` 分裂出来挨个加一下就行。 区间第k小： ``` LL rank(int l, int r, int k) { vector<pair<LL, int> > vp; IT itl = split(l),itr = split(r+1); vp.clear(); for (; itl != itr; ++itl) vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1)); sort(vp.begin(), vp.end()); for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it) { k -= it->second; if (k <= 0) return it->first; } return -1LL; } ``` 暴力取出排序就好了，反正也没有多少段。 ``` LL sum(int l, int r, int ex, int mod) { IT itl = split(l),itr = split(r+1); LL res = 0; for (; itl != itr; ++itl) res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod; return res; } ``` 暴力遍历，快速幂，然后加起来。 那么，这道题就可做了。而且我们交了一发，发现这玩意跑得完全不像暴力，最慢的点是500多ms。 ## 七、一些习题 UESTC的B站讲解里还有另两道题，一道是[CF915E](https://www.luogu.org/problemnew/show/CF915E)，另一道是[BZOJ4293割草](http://ruanx.pw/bzojch/p/4293.html)(权限题)。这两道题的主流做法都是线段树，珂朵莉树也可做。但珂朵莉树仍能体现出代码量较小、易查错的优势，适合作为珂朵莉树的练习题。 ``` #include<cstdio> #include<set> #include<vector> #include<utility> #include<algorithm> #define IT set<node>::iterator using std::set; using std::vector; using std::pair; typedef long long LL; const int MOD7 = 1e9 + 7; const int MOD9 = 1e9 + 9; const int imax_n = 1e5 + 7; LL pow(LL a, LL b, LL mod) { LL res = 1; LL ans = a % mod; while (b) { if (b&1) res = res * ans % mod; ans = ans * ans % mod; b>>=1; } return res; } struct node { int l,r; mutable LL v; node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {} bool operator<(const node& o) const { return l < o.l; } }; set<node> s; IT split(int pos) { IT it = s.lower_bound(node(pos)); if (it != s.end() && it->l == pos) return it; --it; int L = it->l, R = it->r; LL V = it->v; s.erase(it); s.insert(node(L, pos-1, V)); return s.insert(node(pos, R, V)).first; } void add(int l, int r, LL val=1) { IT itl = split(l),itr = split(r+1); for (; itl != itr; ++itl) itl->v += val; } void assign_val(int l, int r, LL val=0) { IT itl = split(l),itr = split(r+1); s.erase(itl, itr); s.insert(node(l, r, val)); } LL rank(int l, int r, int k) { vector<pair<LL, int> > vp; IT itl = split(l),itr = split(r+1); vp.clear(); for (; itl != itr; ++itl) vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1)); std::sort(vp.begin(), vp.end()); for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it) { k -= it->second; if (k <= 0) return it->first; } return -1LL; } LL sum(int l, int r, int ex, int mod) { IT itl = split(l),itr = split(r+1); LL res = 0; for (; itl != itr; ++itl) res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod; return res; } int n, m; LL seed, vmax; LL rnd() { LL ret = seed; seed = (seed * 7 + 13) % MOD7; return ret; } LL a[imax_n]; int main() { scanf("%d %d %lld %lld",&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)); int lines = 0; for (int i =1; i <= m; ++i) { int op = int(rnd() % 4) + 1; int l = int(rnd() % n) + 1; int r = int(rnd() % n) + 1; if (l > r) std::swap(l,r); int x, y; if (op == 3) x = int(rnd() % (r-l+1)) + 1; else x = int(rnd() % vmax) +1; if (op == 4) y = int(rnd() % vmax) + 1; if (op == 1) add(l, r, LL(x)); else if (op == 2) assign_val(l, r, LL(x)); else if (op == 3) printf("%lld\n",rank(l, r, x)); else printf("%lld\n",sum(l, r, x, y)); } return 0; } ```