bzoj4003

题解：

左偏树+pushdown标记加和除都有

按照线段树的方法下传标记

然后就和上一题差不多了

代码：

#include<bits/stdc++.h>
const int N=310000;
using namespace std;  
typedef long long ll;  
struct node  
{  
    int l,r,dis,pos,cnt,c_cnt;  
    ll cadd,cmul,val;  
}a[N];  
ll h[N],v[N];  
int n,m,f[N],out[N],T[N],x,ans1[N],ans2[N],q[N],t[N];  
void pushdown(int x)  
{  
    if (a[x].c_cnt)  
     {  
        a[a[x].l].cnt+=a[x].c_cnt;  
        a[a[x].r].cnt+=a[x].c_cnt;  
        a[a[x].l].c_cnt+=a[x].c_cnt;  
        a[a[x].r].c_cnt+=a[x].c_cnt;  
        a[x].c_cnt=0;  
     }  
    if (a[x].cmul!=1)  
     {  
        a[a[x].l].val*=a[x].cmul;  
        a[a[x].r].val*=a[x].cmul;  
        a[a[x].l].cadd*=a[x].cmul;  
        a[a[x].r].cadd*=a[x].cmul;  
        a[a[x].l].cmul*=a[x].cmul;  
        a[a[x].r].cmul*=a[x].cmul;  
        a[x].cmul=1;  
     }  
    if (a[x].cadd)  
     {  
        a[a[x].l].val+=a[x].cadd;  
        a[a[x].r].val+=a[x].cadd;  
        a[a[x].l].cadd+=a[x].cadd;  
        a[a[x].r].cadd+=a[x].cadd;  
        a[x].cadd=0;  
     }  
}  
int merge(int x,int y)  
{  
    if (!x||!y)return x+y;  
    if (a[x].val>a[y].val)swap(x,y);  
    pushdown(x);  
    a[x].r=merge(a[x].r,y);  
    if (a[a[x].l].dis<a[a[x].r].dis)swap(a[x].l,a[x].r);  
    a[x].dis=a[a[x].r].dis+1;  
    return x;  
}  
void update(int x)  
{  
    int root=T[x];  
    a[root].c_cnt++;  
    a[root].cnt++;  
    if(t[x])  
     {  
        a[root].cmul*=v[x];  
        a[root].cadd*=v[x];  
        a[root].val*=v[x];  
     }  
    else  
     {  
        a[root].cadd+=v[x];  
        a[root].val+=v[x];  
     }  
}  
int main()  
{  
    ll temp;  
    scanf("%d%d",&n,&m);  
    for (int i=1;i<=n;i++)scanf("%lld",&h[i]);  
    for (int i=2;i<=n;i++)  
     {  
        scanf("%d%d%lld",&f[i],&t[i],&v[i]);  
        out[f[i]]++;  
     }   
    a[0].dis=-1;  
    for (int i=1;i<=m;i++)  
     {  
        scanf("%lld%d",&temp,&x);  
        a[i].pos=i,a[i].val=temp,a[i].cmul=1;  
        T[x]=merge(T[x],i);  
     }  
    int l=1,r=0;  
    for (int i=1;i<=n;i++)  
     if (!out[i])q[++r]=i;  
    while (l<=r)  
     {   
        x=q[l++];  
        while (h[x]>a[T[x]].val&&T[x])  
         {  
            ans2[x]++;  
            ans1[a[T[x]].pos]=a[T[x]].cnt;  
            pushdown(T[x]);  
            T[x]=merge(a[T[x]].l,a[T[x]].r);  
         }  
        update(x);  
        T[f[x]]=merge(T[f[x]],T[x]);  
        out[f[x]]--;  
        if (!out[f[x]])q[++r]=f[x];  
     }   
    while (T[0])  
     {  
        ans1[a[T[0]].pos]=a[T[0]].cnt;  
        pushdown(T[0]);  
        T[0]=merge(a[T[0]].l,a[T[0]].r);  
     }  
    for (int i=1;i<=n;i++)printf("%d
",ans2[i]);  
    for (int i=1;i<=m;i++)printf("%d
",ans1[i]);  
    return 0;  
}