用户工具

站点工具


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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/03 20:49]
jxm2001
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/21 22:53] (当前版本)
jxm2001
行 285: 行 285:
 === 题解 === === 题解 ===
  
 +考虑 $\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/左偏树.1601729373.txt.gz · 最后更改: 2020/10/03 20:49 由 jxm2001