用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:左偏树

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/07/09 12:48]
jxm2001 创建
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/21 22:53] (当前版本)
jxm2001
行 3: 行 3:
 ===== 算法简介 ===== ===== 算法简介 =====
  
-一种可并堆,支持 $O(\log n)$ 合并+一种可并堆,支持 $O(\log n)$ 的 $\text{push}$、$\text{pop}$、$\text{merge}$ 操作
  
 ===== 算法思想 ===== ===== 算法思想 =====
  
-定义外节点为左儿子或右儿子为空的节点,$\text{dist}_i$ 表示节点 $i$ 到其子树中最近外节点的距离,规定空节点的 $\text{dist}$ 为 $-1$+定义外节点为左儿子或右儿子为空的节点,$\text{dist}_i$ 表示节点 $i$ 到其子树中最近外节点的距离。
  
-左偏树的定义为对每个节点 $u$ 均满足 $\text{dist}_\text{lson}\ge \text{dist}_\text{rson}$ 的堆。+规定空节点的 $\text{dist}$ 为 $-1$。左偏树的定义为对每个节点 $u$ 均满足 $\text{dist}_\text{lson}\ge \text{dist}_\text{rson}$ 的堆。
  
 左偏树有如下性质 左偏树有如下性质
行 33: 行 33:
  
 [[https://​www.luogu.com.cn/​problem/​P3377|洛谷p3377]] [[https://​www.luogu.com.cn/​problem/​P3377|洛谷p3377]]
 +
 +左偏树的 $\text{pop}$ 操作类似 $\text{fhq treap}$,直接合并被删除节点的左右儿子,但是删除祖先节点会导致并查集出错。
 +
 +具体解决方案为 ''​root[p]=root[node[p].ch[0]]=root[node[p].ch[1]]=rt''​ ,即把原堆顶元素及其儿子节点的祖先节点指向新根节点。
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
 +const int MAXN=1e5+5;​ 
 +struct Left_Heap{ 
 + int root[MAXN];​ 
 + bool del[MAXN];​ 
 + struct Node{ 
 + int id,​val,​dis,​ch[2];​ 
 + bool operator < (const Node &​b)const{return val<​b.val||(val==b.val&&​id<​b.id);​} 
 + }node[MAXN];​ 
 + void build(int *a,int n){ 
 + node[0].dis=-1;​ 
 + _rep(i,​1,​n) 
 + node[i].id=root[i]=i,​node[i].val=a[i];​ 
 +
 + int find_root(int x){return x==root[x]?​x:​root[x]=find_root(root[x]);​} 
 + void merge(int &k,int k1,int k2){ 
 + if(!k1||!k2)return k=k1|k2,​void();​ 
 + if(node[k2]<​node[k1])swap(k1,​k2);​ 
 + merge(node[k=k1].ch[1],​node[k1].ch[1],​k2);​ 
 + if(node[node[k].ch[0]].dis<​node[node[k].ch[1]].dis) 
 + swap(node[k].ch[0],​node[k].ch[1]);​ 
 + node[k].dis=node[node[k].ch[1]].dis+1;​ 
 +
 + void merge(int x,int y){ 
 + if(del[x]||del[y])return;​ 
 + int rt,​p1=find_root(x),​p2=find_root(y);​ 
 + if(p1!=p2){ 
 + merge(rt,​p1,​p2);​ 
 + root[p1]=root[p2]=rt;​ 
 +
 +
 + int top(int x){ 
 + if(del[x])return -1; 
 + return node[find_root(x)].val;​ 
 +
 + void pop(int x){ 
 + if(del[x])return;​ 
 + int rt,​p=find_root(x);​ 
 + merge(rt,​node[p].ch[0],​node[p].ch[1]);​ 
 + root[p]=root[node[p].ch[0]]=root[node[p].ch[1]]=rt;​ 
 + del[p]=true;​ 
 +
 +}heap; 
 +int a[MAXN]; 
 +int main() 
 +
 + int n=read_int(),​m=read_int(),​opt,​x;​ 
 + _rep(i,​1,​n) 
 + a[i]=read_int();​ 
 + heap.build(a,​n);​ 
 + while(m--){ 
 + opt=read_int(),​x=read_int();​ 
 + switch(opt){ 
 + case 1: 
 + heap.merge(x,​read_int());​ 
 + break;​ 
 + case 2: 
 + enter(heap.top(x));​ 
 + heap.pop(x);​ 
 +
 +
 +    return 0; 
 +}
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
行 45: 行 110:
  
 [[https://​www.luogu.com.cn/​problem/​P1456|洛谷p1456]] [[https://​www.luogu.com.cn/​problem/​P1456|洛谷p1456]]
 +
 +=== 题意 ===
 +
 +维护 $n$ 个堆,每个堆一开始只有一个元素,$m$ 个操作。
 +
 +每次选取两个堆,将堆顶元素减半,然后合并。
 +
 +=== 题解 ===
 +
 +修改堆顶元素方法为先合并左右儿子,然后修改堆顶,再次加入。同样要注意并查集的维护。
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
 +const int MAXN=1e5+5;
 +struct Left_Heap{
 + int root[MAXN];
 + struct Node{
 + int id,​val,​dis,​ch[2];​
 + bool operator < (const Node &​b)const{return val>​b.val||(val==b.val&&​id<​b.id);​}
 + }node[MAXN];​
 + void build(int *a,int n){
 + node[0].dis=-1;​
 + _rep(i,​1,​n)
 + node[i].id=root[i]=i,​node[i].val=a[i],​node[i].ch[0]=node[i].ch[1]=node[i].dis=0;​
 + }
 + int find_root(int x){return x==root[x]?​x:​root[x]=find_root(root[x]);​}
 + void merge(int &k,int k1,int k2){
 + if(!k1||!k2)return k=k1|k2,​void();​
 + if(node[k2]<​node[k1])swap(k1,​k2);​
 + merge(node[k=k1].ch[1],​node[k1].ch[1],​k2);​
 + if(node[node[k].ch[0]].dis<​node[node[k].ch[1]].dis)
 + swap(node[k].ch[0],​node[k].ch[1]);​
 + node[k].dis=node[node[k].ch[1]].dis+1;​
 + }
 + int merge(int x,int y){
 + int rt,​p1=find_root(x),​p2=find_root(y);​
 + if(p1==p2)return -1;
 + update(p1);​update(p2);​
 + p1=find_root(x),​p2=find_root(y);​
 + merge(rt,​p1,​p2);​
 + root[p1]=root[p2]=rt;​
 + return node[rt].val;​
 + }
 + void update(int rt){
 + int temp,Root;
 + merge(temp,​node[rt].ch[0],​node[rt].ch[1]);​
 + node[rt].val>>​=1;​node[rt].ch[0]=node[rt].ch[1]=node[rt].dis=0;​
 + merge(Root,​temp,​rt);​
 + root[Root]=root[rt]=Root;​
 + }
 +}heap;
 +int a[MAXN];
 +int main()
 +{
 + int n,m,x,y;
 + while(~scanf("​%d",&​n)){
 + _rep(i,​1,​n)
 + a[i]=read_int();​
 + heap.build(a,​n);​
 + m=read_int();​
 + _rep(i,​1,​m){
 + x=read_int(),​y=read_int();​
 + enter(heap.merge(x,​y));​
 + }
 + }
 +    return 0;
 +}
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
  
 +==== 习题二 ====
 +
 +[[https://​www.luogu.com.cn/​problem/​P4331|洛谷p4331]]
 +
 +=== 题意 ===
 +
 +给定一个序列 $A$,要求构造一个严格单增序列 $B$,满足 $\sum_{i=1}^n |a_i-b_i|$ 取最小值。
 +
 +=== 题解 ===
 +
 +首先将 $a_i$ 变为 $a_i-i$,于是问题转化为构造一个不减序列 $B$。
 +
 +单独考虑区间 $[x,​x]$,显然答案为 $b_x=a_x$。对区间 $C_1[x,​y],​C_2[y+1,​z]$,假设区间 $C_1$ 答案为 $c_1$,区间 $C_2$ 答案为 $c_2$。
 +
 +若 $c_1\le c_2$,显然不需要修改,若 $c_1\gt c_2$,发现取区间 $[x,z]$ 的中位数作为区间 $[x,z]$ 的答案显然最优。
 +
 +考虑单调栈维护中位数单调不减的区间,同时左偏堆(大根堆)维护中位数。
 +
 +对左偏堆弹出一半的数即可得到中位数,可以证明在该算法下该操作不会导致答案错误,时间复杂度 $O(n\log n)$。
 +
 +<hidden 查看代码>​
 +<code cpp>
 +const int MAXN=1e6+5;
 +namespace Left_Heap{
 + struct Node{
 + int val,​dis,​ch[2];​
 + bool operator < (const Node &​b)const{return val<​b.val;​}
 + }node[MAXN];​
 + void init(){node[0].dis=-1;​}
 + void merge(int &k,int k1,int k2){
 + if(!k1||!k2)return k=k1|k2,​void();​
 + if(node[k1]<​node[k2])swap(k1,​k2);​
 + merge(node[k=k1].ch[1],​node[k1].ch[1],​k2);​
 + if(node[node[k].ch[0]].dis<​node[node[k].ch[1]].dis)
 + swap(node[k].ch[0],​node[k].ch[1]);​
 + node[k].dis=node[node[k].ch[1]].dis+1;​
 + }
 +};
 +struct Heap{
 + int tot,sz,rt;
 + int top(){return Left_Heap::​node[rt].val;​}
 + void pop(){
 + Left_Heap::​merge(rt,​Left_Heap::​node[rt].ch[0],​Left_Heap::​node[rt].ch[1]);​
 + sz--;
 + }
 + void merge(Heap y){
 + Left_Heap::​merge(rt,​rt,​y.rt);​
 + tot+=y.tot;​
 + sz+=y.sz;
 + }
 +}heap[MAXN];​
 +int a[MAXN];
 +int main()
 +{
 + Left_Heap::​init();​
 + int n=read_int(),​top=0;​
 + _rep(i,​1,​n){
 + Left_Heap::​node[i].val=a[i]=read_int()-i;​
 + heap[++top]=Heap{1,​1,​i};​
 + while(top>​1&&​heap[top-1].top()>​heap[top].top()){
 + top--;
 + heap[top].merge(heap[top+1]);​
 + while(heap[top].sz>​(heap[top].tot+1)/​2)
 + heap[top].pop();​
 + }
 + }
 + int pos=1;
 + LL ans=0;
 + _rep(i,​1,​top){
 + _for(j,​0,​heap[i].tot){
 + ans+=abs(a[pos]-heap[i].top());​
 + pos++;
 + }
 + }
 + enter(ans);​
 + pos=1;
 + _rep(i,​1,​top){
 + _for(j,​0,​heap[i].tot){
 + space(heap[i].top()+pos);​
 + pos++;
 + }
 + }
 + return 0;
 +}
 +</​code>​
 +</​hidden>​
 +
 +==== 习题三 ====
 +
 +[[https://​www.luogu.com.cn/​problem/​P3261|洛谷p3261]]
 +
 +=== 题意 ===
 +
 +给定一棵以 $1$ 为根的树,每个点拥有属性 $(h_i,​a_i,​v_i)$。同时给定 $m$ 个士兵,每个士兵初始时在 $s_i$ 号点,且拥有 $c_i$ 点生命。 ​
 +
 +当士兵 $i$ 处在点 $j$ 时,如果 $c_i\lt h_j$,则该士兵在该点死亡。
 +
 +否则该士兵生命产生变化。具体得,如果 $a_i=0$ 则士兵生命增加 $v_i$,如果 $a_i=1$ 则士兵生命乘以 $v_i$。
 +
 +如果士兵未死亡,则士兵通过当前结点且继续前往该结点的父节点。
 +
 +询问每个结点死亡的士兵数和每个士兵最终通过的结点数。数据保证士兵任意时刻生命值不爆 $\text{long long}$ 且如果 $a_i=1$ 则 $v_i\gt 0$。
 +
 +=== 题解 ===
 +
 +考虑 $\text{dfs}$ 遍历城市,左偏树合并子节点士兵信息,每次弹出堆顶所有 $c\lt h$ 的结点,同时更新答案。
 +
 +对于修改操作,类似线段树懒标记处理即可。由于 $a_i=1$ 时保证 $v_i\gt 0$,所有结点的相对大小不改变,所有懒标记处理可以保证正确性。
 +
 +合并操作总复杂度 $(n\log m)$,弹出操作总复杂度 $O(m\log m)$,修改操作总时间复杂度 $O(n)$。于是总时间复杂度 $O((n+m)\log m)$。
 +
 +<hidden 查看代码>​
 +<code cpp>
 +const int MAXN=3e5+5;
 +namespace Left_Heap{
 + struct Node{
 + LL val,​lazy[2];​
 + int idx,​dis,​ch[2];​
 + void set(int id,LL v){
 + idx=id,​val=v;​
 + lazy[0]=1,​lazy[1]=0;​
 + }
 + bool operator < (const Node &​b)const{return val<​b.val||(val==b.val&&​idx<​b.idx);​}
 + }node[MAXN];​
 + void init(){node[0].dis=-1;​}
 + void push_tag(int k,LL tag1,LL tag2){
 + if(!k)return;​
 + node[k].val=node[k].val*tag1+tag2;​
 + node[k].lazy[0]=node[k].lazy[0]*tag1;​
 + node[k].lazy[1]=node[k].lazy[1]*tag1+tag2;​
 + }
 + void push_down(int k){
 + push_tag(node[k].ch[0],​node[k].lazy[0],​node[k].lazy[1]);​
 + push_tag(node[k].ch[1],​node[k].lazy[0],​node[k].lazy[1]);​
 + node[k].lazy[0]=1,​node[k].lazy[1]=0;​
 + }
 + void merge(int &k,int k1,int k2){
 + if(!k1||!k2)return k=k1|k2,​void();​
 + push_down(k1);​push_down(k2);​
 + if(node[k2]<​node[k1])swap(k1,​k2);​
 + merge(node[k=k1].ch[1],​node[k1].ch[1],​k2);​
 + if(node[node[k].ch[0]].dis<​node[node[k].ch[1]].dis)
 + swap(node[k].ch[0],​node[k].ch[1]);​
 + node[k].dis=node[node[k].ch[1]].dis+1;​
 + }
 +};
 +struct Heap{
 + int sz,rt;
 + pair<​int,​LL>​ top(){return make_pair(Left_Heap::​node[rt].idx,​Left_Heap::​node[rt].val);​}
 + void pop(){
 + Left_Heap::​push_down(rt);​
 + Left_Heap::​merge(rt,​Left_Heap::​node[rt].ch[0],​Left_Heap::​node[rt].ch[1]);​
 + sz--;
 + }
 + void push(int idx,LL v){
 + Left_Heap::​node[idx].set(idx,​v);​
 + Left_Heap::​merge(rt,​rt,​idx);​
 + sz++;
 + }
 + void merge(Heap y){
 + Left_Heap::​merge(rt,​rt,​y.rt);​
 + sz+=y.sz;
 + }
 + Heap(){sz=rt=0;​}
 +}heap[MAXN];​
 +struct Edge{
 + int to,next;
 +}edge[MAXN];​
 +int head[MAXN],​edge_cnt;​
 +void Insert(int u,int v){
 + edge[++edge_cnt]=Edge{v,​head[u]};​
 + head[u]=edge_cnt;​
 +}
 +int a[MAXN],​s[MAXN],​d[MAXN],​ans1[MAXN],​ans2[MAXN];​
 +LL h[MAXN],​tag[MAXN];​
 +void dfs(int u){
 + for(int i=head[u];​i;​i=edge[i].next){
 + int v=edge[i].to;​
 + d[v]=d[u]+1;​
 + dfs(v);
 + heap[u].merge(heap[v]);​
 + }
 + while(heap[u].sz&&​heap[u].top().second<​h[u]){
 + ans1[u]++;​
 + ans2[heap[u].top().first]=d[u];​
 + heap[u].pop();​
 + }
 + if(heap[u].sz){
 + if(a[u])
 + Left_Heap::​push_tag(heap[u].rt,​tag[u],​0);​
 + else
 + Left_Heap::​push_tag(heap[u].rt,​1,​tag[u]);​
 + }
 +}
 +int main()
 +{
 + Left_Heap::​init();​
 + int n=read_int(),​m=read_int();​
 + _rep(i,​1,​n)
 + h[i]=read_LL();​
 + _rep(i,​2,​n){
 + Insert(read_int(),​i);​
 + a[i]=read_int(),​tag[i]=read_LL();​
 + }
 + _rep(i,​1,​m){
 + LL c=read_LL();​
 + s[i]=read_int();​
 + heap[s[i]].push(i,​c);​
 + }
 + d[1]=1;
 + dfs(1);
 + _rep(i,​1,​n)
 + enter(ans1[i]);​
 + _rep(i,​1,​m)
 + enter(d[s[i]]-ans2[i]);​
 + return 0;
 +}
 +</​code>​
 +</​hidden>​
2020-2021/teams/legal_string/jxm2001/左偏树.1594270123.txt.gz · 最后更改: 2020/07/09 12:48 由 jxm2001