【左偏树】 [JLOI2015]城池攻占

 1 #include<bits/stdc++.h>
 2 #define int long long 
 3 #define writeln(x)  write(x),puts("")
 4 #define writep(x)   write(x),putchar(' ')
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }void write(int x){
12     if(x<0) putchar('-'),x=-x;
13     if(x>9) write(x/10);
14     putchar(x%10+'0');
15 }const int M = 3e5+5;
16 int a[M],h[M],v[M],c[M],n,m,head[M],ver[M<<1],nxt[M<<1],tot,val[M],son[M][2],dis[M],fa[M];
17 int mul[M],add[M],dep[M],ans1[M],ans2[M];
18 inline void Add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
19 #define ls son[x][0]
20 #define rs son[x][1]
21 inline void Down(int x,int mull,int addd){
22     if(!x) return;
23     val[x]*=mull,val[x]+=addd;
24     mul[x]*=mull,add[x]*=mull,add[x]+=addd;
25 }
26 inline void Push_Down(int x){
27     Down(ls,mul[x],add[x]);
28     Down(rs,mul[x],add[x]);
29     mul[x]=1,add[x]=0;
30 }
31 int Merge(int x,int y){
32     if(!x||!y) return x|y;
33     Push_Down(x);Push_Down(y);
34     if(val[x]>val[y]) swap(x,y);
35     rs=Merge(rs,y);
36     if(dis[ls]<dis[rs]) swap(ls,rs);
37     dis[x]=dis[rs]+1;
38     return x;
39 }int Pop(int x){return Merge(ls,rs);}
40 void dfs(int x){
41     for(int i=head[x];i;i=nxt[i]){
42         dep[ver[i]]=dep[x]+1;
43         dfs(ver[i]);
44         fa[x]=Merge(fa[x],fa[ver[i]]);
45     }
46     while(fa[x]&&val[fa[x]]<h[x]){
47         Push_Down(fa[x]);
48         ans1[x]++;ans2[fa[x]]=dep[c[fa[x]]]-dep[x];
49         fa[x]=Pop(fa[x]);
50     }if(a[x]) Down(fa[x],v[x],0);
51     else Down(fa[x],1,v[x]);
52 }
53 signed main(){
54     n=read(),m=read();
55     for(int i=1;i<=n;i++) h[i]=read();
56     for(int x,i=2;i<=n;i++)    x=read(),Add(x,i),a[i]=read(),v[i]=read();
57     for(int i=1;i<=m;i++){
58         val[i]=read(),c[i]=read(),mul[i]=1;
59         fa[c[i]]=Merge(fa[c[i]],i);
60     }dep[1]=1,dfs(1);
61     while(fa[1]){
62         Push_Down(fa[1]);
63         ans2[fa[1]]=dep[c[fa[1]]];
64         fa[1]=Pop(fa[1]);
65     }
66     for(int i=1;i<=n;i++) writeln(ans1[i]);
67     for(int i=1;i<=n;i++) writeln(ans2[i]);
68     return 0;
69 }