bzoj 4003

左偏树。。。

打两个标记。。。和线段树一样，先下放cheng再下放*。

每回合并子树就行了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define N 300010

 #define int long long

 using namespace std;

 int n,m,h[N];

 int b[N],v[N];

 int s[N],root[N];

 vector<int>qi[N];

 int c[N],ans[N],ans2[N];

 int head[N],nxt[N],ver[N],tot;

 void add(int a,int d)

 {

     tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=d;return ;

 }

 struct node

 {

     int l,r,w,d,lazy1,lazy2;

     int pre;

     node()

     {

         lazy2=;

     }

 }a[N*];int cnt;

 int dep[N];

 void push_down(int x)

 {

     int t1=a[x].l;int t2=a[x].r;

     if(t1)

     {

         a[t1].w*=a[x].lazy2,a[t1].lazy1*=a[x].lazy2,a[t1].lazy2*=a[x].lazy2;

         a[t1].w+=a[x].lazy1;

         a[t1].lazy1+=a[x].lazy1;

     }

     if(t2)

     {

         a[t2].w*=a[x].lazy2,a[t2].lazy1*=a[x].lazy2,a[t2].lazy2*=a[x].lazy2;

         a[t2].w+=a[x].lazy1;

         a[t2].lazy1+=a[x].lazy1;

     }

     a[x].lazy1=;

     a[x].lazy2=;

     return ;

 }

 int merge(int x,int y)

 {

     if(!x||!y)return x+y;

     if(a[x].w>a[y].w)swap(x,y);

     push_down(x);

     a[x].r=merge(a[x].r,y);

     if(a[a[x].l].d<a[a[x].r].d)swap(a[x].l,a[x].r);

     a[x].d=a[a[x].r].d+;

     return x;

 }

 void dfs(int x)

 {

     root[x]=;

     for(int i=;i<qi[x].size();i++)

     {

         a[++cnt].pre=qi[x][i];a[cnt].w=s[qi[x][i]];root[x]=merge(root[x],cnt);

     }

     for(int i=head[x];i;i=nxt[i])

     {

         dep[ver[i]]=dep[x]+;

         dfs(ver[i]);

         root[x]=merge(root[x],root[ver[i]]);

     }

     while(root[x]&&a[root[x]].w<h[x])

     {

         ans[x]++;

         int y=a[root[x]].pre;

         ans2[y]=dep[c[y]]-dep[x];

         push_down(root[x]);

         root[x]=merge(a[root[x]].l,a[root[x]].r);

     }

     if(root[x])

     {

         if(!b[x])

         {

             a[root[x]].w+=v[x];

             a[root[x]].lazy1+=v[x];

         }

         else

         {

             a[root[x]].w*=v[x];

             a[root[x]].lazy1*=v[x];

             a[root[x]].lazy2*=v[x];

         }

     }

     return ;

 }

 signed main()

 {

     scanf("%lld%lld",&n,&m);

     for(int i=;i<=n;i++)scanf("%lld",&h[i]);

     int t1;

     for(int i=;i<=n;i++)

     {

         scanf("%lld",&t1);

         add(t1,i);

         scanf("%lld%lld",&b[i],&v[i]);

     }

     for(int i=;i<=m;i++)

     {

         scanf("%lld%lld",&s[i],&t1);

         qi[t1].push_back(i);c[i]=t1;

     }

     dep[]=;

     dfs();

     while(root[]!=)

     {

         int y=a[root[]].pre;

         ans2[y]=dep[c[y]]-dep[]+;

         push_down(root[]);

         root[]=merge(a[root[]].l,a[root[]].r);

     }

     for(int i=;i<=n;i++)printf("%lld\n",ans[i]);

     for(int i=;i<=m;i++)printf("%lld\n",ans2[i]);

     return ;

 }