这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/07/09 15:52] 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}$ 的堆。 |
左偏树有如下性质 | 左偏树有如下性质 | ||
行 40: | 行 40: | ||
<hidden 查看代码> | <hidden 查看代码> | ||
<code cpp> | <code cpp> | ||
- | #include <iostream> | ||
- | #include <cstdio> | ||
- | #include <cstdlib> | ||
- | #include <algorithm> | ||
- | #include <string> | ||
- | #include <sstream> | ||
- | #include <cstring> | ||
- | #include <cctype> | ||
- | #include <cmath> | ||
- | #include <vector> | ||
- | #include <set> | ||
- | #include <map> | ||
- | #include <stack> | ||
- | #include <queue> | ||
- | #include <ctime> | ||
- | #include <cassert> | ||
- | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
- | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
- | #define mem(a,b) memset(a,b,sizeof(a)) | ||
- | using namespace std; | ||
- | typedef long long LL; | ||
- | inline int read_int(){ | ||
- | int t=0;bool sign=false;char c=getchar(); | ||
- | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
- | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
- | return sign?-t:t; | ||
- | } | ||
- | inline LL read_LL(){ | ||
- | LL t=0;bool sign=false;char c=getchar(); | ||
- | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
- | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
- | return sign?-t:t; | ||
- | } | ||
- | inline char get_char(){ | ||
- | char c=getchar(); | ||
- | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
- | return c; | ||
- | } | ||
- | inline void write(LL x){ | ||
- | register char c[21],len=0; | ||
- | if(!x)return putchar('0'),void(); | ||
- | if(x<0)x=-x,putchar('-'); | ||
- | while(x)c[++len]=x%10,x/=10; | ||
- | while(len)putchar(c[len--]+48); | ||
- | } | ||
- | inline void space(LL x){write(x),putchar(' ');} | ||
- | inline void enter(LL x){write(x),putchar('\n');} | ||
const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
struct Left_Heap{ | struct Left_Heap{ | ||
行 170: | 行 123: | ||
<hidden 查看代码> | <hidden 查看代码> | ||
<code cpp> | <code cpp> | ||
- | #include <iostream> | ||
- | #include <cstdio> | ||
- | #include <cstdlib> | ||
- | #include <algorithm> | ||
- | #include <string> | ||
- | #include <sstream> | ||
- | #include <cstring> | ||
- | #include <cctype> | ||
- | #include <cmath> | ||
- | #include <vector> | ||
- | #include <set> | ||
- | #include <map> | ||
- | #include <stack> | ||
- | #include <queue> | ||
- | #include <ctime> | ||
- | #include <cassert> | ||
- | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
- | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
- | #define mem(a,b) memset(a,b,sizeof(a)) | ||
- | using namespace std; | ||
- | typedef long long LL; | ||
- | inline int read_int(){ | ||
- | int t=0;bool sign=false;char c=getchar(); | ||
- | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
- | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
- | return sign?-t:t; | ||
- | } | ||
- | inline LL read_LL(){ | ||
- | LL t=0;bool sign=false;char c=getchar(); | ||
- | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
- | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
- | return sign?-t:t; | ||
- | } | ||
- | inline char get_char(){ | ||
- | char c=getchar(); | ||
- | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
- | return c; | ||
- | } | ||
- | inline void write(LL x){ | ||
- | register char c[21],len=0; | ||
- | if(!x)return putchar('0'),void(); | ||
- | if(x<0)x=-x,putchar('-'); | ||
- | while(x)c[++len]=x%10,x/=10; | ||
- | while(len)putchar(c[len--]+48); | ||
- | } | ||
- | inline void space(LL x){write(x),putchar(' ');} | ||
- | inline void enter(LL x){write(x),putchar('\n');} | ||
const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
struct Left_Heap{ | struct Left_Heap{ | ||
行 274: | 行 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> |