1890. Money out of Thin Air（线段树 dfs转换区间）

将树的每个节点都转换为区间的形式然后再利用线段树对结点更新这题用了延迟标记相对普通线段树多了dfs的转换把所要求的转换为某段区间
RE了N次最后没办法了记得有个加栈的语句拿来加上A了。。
  1 #pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<algorithm>
  8 using namespace std;
  9 #define N 50010
 10 #define LL long long
 11 vector<int>w[N];
 12 LL lleft[N],rright[N],po[N],c[N],cnt;
 13 LL o[N];
 14 LL s[N<<2],te[N<<2];
 15 void up(int w)
 16 {
 17     s[w] = s[w<<1]+s[w<<1|1];
 18 }
 19 void build(int l,int r,int w)
 20 {
 21     if(l==r)
 22     {
 23         s[w] = c[l];
 24         return ;
 25     }
 26     int m = (l+r)>>1;
 27     build(l,m,w<<1);
 28     build(m+1,r,w<<1|1);
 29     up(w);
 30 }
 31 void pushdown(int w,int d)
 32 {
 33     if(te[w])
 34     {
 35         te[w<<1] += te[w];
 36         te[w<<1|1]+=te[w];
 37         s[w<<1] += (d-d/2)*te[w];
 38         s[w<<1|1]+=d/2*te[w];
 39         te[w] = 0;
 40     }
 41 }
 42 void update(int a,int b,LL v,int l,int r,int w)
 43 {
 44     if(a<=l&&b>=r)
 45     {
 46         te[w] += v;
 47         s[w] += v*(r-l+1);
 48         return ;
 49     }
 50     pushdown(w,r-l+1);
 51     int m = (l+r)>>1;
 52     if(a<=m)
 53     update(a,b,v,l,m,w<<1);
 54     if(b>m)
 55     update(a,b,v,m+1,r,w<<1|1);
 56     up(w);
 57 }
 58 LL query(int a,int b,int l,int r,int w)
 59 {
 60     if(a<=l&&b>=r)
 61     {
 62         return s[w];
 63     }
 64     pushdown(w,r-l+1);
 65     int m = (l+r)>>1;
 66     LL re =0;
 67     if(a<=m)
 68     re+=query(a,b,l,m,w<<1);
 69     if(b>m)
 70     re+=query(a,b,m+1,r,w<<1|1);
 71     return re;
 72 }
 73 void dfs(int u)
 74 {
 75     int i;
 76     for(i = 0 ; i < (int)w[u].size() ; i++)
 77     {
 78         int v = w[u][i];
 79         dfs(v);
 80         if(lleft[u]==-1)
 81         lleft[u] = lleft[v];
 82         else
 83         lleft[u] = min(lleft[v],lleft[u]);
 84         if(rright[u]==-1)
 85         rright[u] = rright[v];
 86         else
 87         rright[u] = max(rright[u],rright[v]);
 88     }
 89     cnt++;
 90     c[cnt] = o[u];
 91     po[u] = cnt;
 92     if(lleft[u]==-1)
 93     lleft[u] = cnt;
 94     else
 95     lleft[u] = min(lleft[u],cnt);
 96     if(rright[u]==-1)
 97     rright[u] = cnt;
 98     else
 99     rright[u] = max(rright[u],cnt);
100 }
101 int main()
102 {
103     int n,q,s0,x,u,v,i;
104     char ss[20];
105     memset(lleft,-1,sizeof(lleft));
106     memset(rright,-1,sizeof(rright));
107     scanf("%d%d%d",&n,&q,&s0);
108     o[1] = s0;
109     for(i = 0 ; i <= n ; i++)
110     w[i].clear();
111     for(i = 2; i <= n ; i++)
112     {
113         scanf("%d%d",&u,&v);
114         u++;
115         w[u].push_back(i);
116         o[i] = v;
117     }
118     dfs(1);
119     build(1,n,1);
120     while(q--)
121     {
122         scanf("%s%d%d%d",ss,&x,&u,&v);
123         x++;
124         if(ss[0]=='e')
125         {
126             int pp = po[x];
127             LL tx = query(pp,pp,1,n,1);
128             if(tx<u)
129             update(pp,pp,v,1,n,1);
130         }
131         else if(ss[0]=='d')
132         {
133             int ll = lleft[x];
134             int rr = rright[x];
135             int nu = rr-ll+1;
136             LL tx = query(ll,rr,1,n,1);
137             if(1.0*tx/nu<u)
138             update(ll,rr,v,1,n,1);
139         }
140     }
141     for(i = 1; i <= n ; i++)
142     printf("%lld
",query(po[i],po[i],1,n,1));
143     return 0;
144 }
View Code