用户工具

站点工具


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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/03 19:20]
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}$ 的堆。
  
 左偏树有如下性质 左偏树有如下性质
行 262: 行 262:
  }  }
  }  }
 + 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;  return 0;
 } }
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
2020-2021/teams/legal_string/jxm2001/左偏树.1601724009.txt.gz · 最后更改: 2020/10/03 19:20 由 jxm2001