题目
luogu
原来左偏树真的能懒惰下放
那这篇博客应该要咕咕了
一开始我按照那篇博客想了一下，感觉emm，还是瞄了一眼看到了pushdown
思路
类似线段树2的pushdown，不过是套在了左偏树
其他也就没啥了
ans1直接删除统计
ans2就初始深度-死亡深度(树的路径唯一嘛)
ps:深度可以在dfs的时候顺便求出来
就这样
错误&&反思
一开始20，死活不对
最后又是手贱n写成m
还是20
又经过漫长debug(不会造树data的伤感)
无奈去看题解，长着差不多的模样
最后
while(val[rt[u]] < fangyu[u] && rt[u]) {
pushdown(rt[u]);
ans2[rt[u]]=dep[S[rt[u]]]-dep[u];
ans1[u]++;
rt[u]=merge(ch[rt[u]][0],ch[rt[u]][1]);
}
居然一个pushdown就OK了
我想着是merge就会pushdown的，就没写、、、、
代码
#include <iostream>
#include <cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=3e5+7;
typedef long long ll;
inline ll read() {
ll x=0,f=1;char s=getchar();
for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
struct node {
int v,nxt;
}e[maxn];
int head[maxn],tot;
void add_edge(int u,int v) {
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
int n,m,cnt,rt[maxn],ch[maxn][2],dis[maxn],ans1[maxn],ans2[maxn],dep[maxn];
ll A[maxn],B[maxn],fangyu[maxn],ad[maxn],mu[maxn],val[maxn];
void da_tag(int x,ll a,ll b) {
val[x]=val[x]*a+b;
ad[x]=ad[x]*a+b;
mu[x]*=a;
}
void pushdown(int x) {
if(ad[x]==0&&mu[x]==1) return;
int it_a=ch[x][0],it_b=ch[x][1];
da_tag(it_a,mu[x],ad[x]);
da_tag(it_b,mu[x],ad[x]);
ad[x]=0,mu[x]=1;
}
int merge(int x,int y) {
if(!x || !y) return x+y;
pushdown(x),pushdown(y);
if(val[x]>val[y]) swap(x,y);
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int S[maxn];
int dfs(int u,int f) {
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].nxt) {
int tmp=dfs(e[i].v,u);
rt[u]=merge(rt[u],tmp);
}
while(val[rt[u]] < fangyu[u] && rt[u]) {
pushdown(rt[u]);
ans2[rt[u]]=u;
ans1[u]++;
rt[u]=merge(ch[rt[u]][0],ch[rt[u]][1]);
}
da_tag(rt[u],A[u],B[u]);
return rt[u];
}
int main() {
n=read(),m=read();
FOR(i,1,m) mu[i]=1;
FOR(i,1,n) fangyu[i]=read();
FOR(i,2,n) {
int x=read(),y=read();
add_edge(x,i);
A[i]=1;
if(y) A[i]=read();
else B[i]=read();
}
FOR(i,1,m) {
ll x=read();S[i]=read();
val[i]=x;
rt[S[i]]=merge(rt[S[i]],i);
}
dfs(1,0);
FOR(i,1,n) cout<<ans1[i]<<"\n";
FOR(i,1,m) cout<<dep[S[i]]-dep[ans2[i]]<<"\n";
return 0;
}