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

刺骨的言语ヽ痛彻心扉 2023-06-01 06:08 27阅读 0赞

原来左偏树还可以打tag，get了

和线段树打tag一样，时不时Push\_Down就好了

然后这里显然也是要先乘法后加法的

tag打上了之后还是其他一般左偏树差不多，有些细节注意一下

然后开 long long!!!

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 }

转载于:https://www.cnblogs.com/zhenglw/p/11245283.html