用户工具

站点工具


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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/03 17:22]
jxm2001 [习题二]
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/21 22:53] (当前版本)
jxm2001
行 7: 行 7:
 ===== 算法思想 ===== ===== 算法思想 =====
  
-定义外节点为左儿子或右儿子为空的节点,$\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}$ 的堆。
  
 左偏树有如下性质 左偏树有如下性质
行 196: 行 196:
 若 $c_1\le c_2$,显然不需要修改,若 $c_1\gt c_2$,发现取区间 $[x,z]$ 的中位数作为区间 $[x,z]$ 的答案显然最优。 若 $c_1\le c_2$,显然不需要修改,若 $c_1\gt c_2$,发现取区间 $[x,z]$ 的中位数作为区间 $[x,z]$ 的答案显然最优。
  
-考虑左偏堆(大根堆)维护中位数。对区间 $[x,​y]$,弹出一半的数即可得到中位数。+考虑单调栈维护中位数单调不减的区间,同时左偏堆(大根堆)维护中位数。
  
-需要合并区间 ​$C_1,C_2$ 时,由于 $$+对左偏堆弹出一半的数即可得到中位数,可以证明在该算法下该操作不会导致答案错误,时间复杂度 $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/左偏树.1601716961.txt.gz · 最后更改: 2020/10/03 17:22 由 jxm2001