百度云资源搜索网站,wordpress 用户权限,wordpress主题首页怎么修改,做问卷的网站小时候听说过珂朵莉树的大名#xff0c;奈何当时没有专业知识看不懂。最近正好想起来了#xff0c;来补上这个遗憾。
珂朵莉树#xff08;Chtholly Tree#xff09;又叫老司机树#xff08;ODT#xff0c;Old Driver Tree#xff09;。多年前#xff0c;一位用户 Old …小时候听说过珂朵莉树的大名奈何当时没有专业知识看不懂。最近正好想起来了来补上这个遗憾。
珂朵莉树Chtholly Tree又叫老司机树ODTOld Driver Tree。多年前一位用户 Old Driver 在通过本题 Willem, Chtholly and Seniorious 时给出了不同于线段树的暴力解法也就是今天的 ODT。它以 s e t set set 为容器使用 s p l i t split split 和 a s s ♂ i g n ass♂ign ass♂ign 两个核心函数以及极其暴力的思想来实现。思路清晰简单码量少相对于线段树。
不过珂朵莉树还是很容易卡掉的在面对随机数据和优化一些东西的时候才比较不容易被卡。不过这个好写确实是好写有时间可以看看 不会花太多时间的 。
珂朵莉树讲解 梦的开始 珂朵莉树板题
这个题由于是使用随机数据生成器来生成数据所以数据和操作都是随机的有 1 4 \frac14 41 的概率会将区间直接赋值为一个数正好对应 a s s i g n assign assign 函数可以把区间合并成一个点的功能大大降低时间复杂度。因此可以使用珂朵莉树。
code
三个注意点
一
val 定义时需要使用 mutable 来修饰表示是可变的数据不然一些版本会报错 [Error] assignment of member ODT::Node::val in read-only object 我估计应该是一些版本不允许迭代器直接修改参数值也就是迭代器有 const 属性
二
讲解的博客中也提到了SIT it2split(r1),it1split(l);中顺序不应改变先 split(r1)再 split(l)。否则如果 l l l 和 r 1 r1 r1 在同一个节点上就会导致 split(l) 指向的节点被删掉迭代器失效。
一般来说如果删除的是set中迭代器指向的元素那么这个迭代器将会失效。如果删除的是其他元素通常来说set中的其他迭代器应该保持有效。但是注意进行容器修改操作后所有迭代器都可能失效迭代器失效通常与容器的结构变化有关。
三
build() 函数中的 s.insert(Node(n1,n1,0)); 语句应当尽量写上。否则当 split(n1) 的时候就会加入两个节点范围分别是 [ l , n ] , [ n 1 , n ] [l,n],[n1,n] [l,n],[n1,n]。
而且加入这个语句后s.lower_bound() 一定不会访问到 s.end() 可以少写点判断代码。
#include iostream
#include cstdio
#include set
#include vector
#include algorithm
using namespace std;const int maxn1e55;
typedef long long ll;ll n,m,seed,vm;ll rnd(){ll retseed;seed(7ll*seed13)%1000000007ll;return ret;
}ll qpow(ll a,ll b,ll mod){ll ans1,basea;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}struct ODT{#define SIT setNode::iteratorstruct Node{int l,r;mutable ll val;Node(int l,int r-1,ll val0):l(l),r(r),val(val){};bool operator(const Node x)const{return lx.l;}};setNode s;void build(int n){for(int i1;in;i)s.insert(Node(i,i,rnd()%vm1));s.insert(Node(n1,n1,0));}SIT split(int pos){SIT its.lower_bound(Node(pos));if(it!s.end() it-lpos){return it;}it--;int lit-l,rit-r;ll valit-val;s.erase(it);s.insert(Node(l,pos-1,val));return s.insert(Node(pos,r,val)).first;}void assign(int l,int r,ll x){SIT it2split(r1),it1split(l);s.erase(it1,it2);s.insert(Node(l,r,x));}void add(int l,int r,ll x){SIT it2split(r1),it1split(l);for(;it1!it2;it1)it1-valx;}ll rk(int l,int r,ll k){SIT it2split(r1),it1split(l);vectorpairll,int t;t.clear();for(;it1!it2;it1)t.push_back(pairll,int(it1-val,it1-r-it1-l1));sort(t.begin(),t.end());for(auto x:t){if(x.secondk)return x.first;else k-x.second;}}ll pw(int l,int r,ll x,ll mod){SIT it2split(r1),it1split(l);ll ans0;for(;it1!it2;it1){ans(ans1ll*(it1-r-it1-l1)*qpow(it1-val%mod,x,mod)%mod)%mod;}return ans;}void print(){for(auto x:s){printf([%d,%d] val%d\n,x.l,x.r,x.val);}puts();}#undef SIT
}tr;int main(){cinnmseedvm;tr.build(n);
// tr.print();for(int i1;im;i){ll op,l,r,x,y;oprnd()%41;lrnd()%n1;rrnd()%n1;if(lr)swap(l,r);if(op3)xrnd()%(r-l1)1;else xrnd()%vm1;if(op4)yrnd()%vm1;if(op1){tr.add(l,r,x);}else if(op2){tr.assign(l,r,x);}else if(op3){couttr.rk(l,r,x)endl;}else {couttr.pw(l,r,x,y)endl;}
// tr.print();}return 0;
}
