用户工具

站点工具


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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/07/26 12:45]
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}$ 的堆。
  
 左偏树有如下性质 左偏树有如下性质
行 180: 行 180:
 </​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/左偏树.1595738742.txt.gz · 最后更改: 2020/07/26 12:45 由 jxm2001