51Nod 1199 Money out of Thin Air (dfs 순차 가선 세그먼트 트 리)
또 오후 내 내...
사고의 방향
트 리 의 우선 순 서 는 선분 트 리 의 한 구간 에 딱 맞 게 옮 겨 다 니 며 이 점 을 이용 하여 dfs 로 순 서 를 만 든 다음 에 선분 트 리 를 만들어 수정 을 조회 하면 됩 니 다.
1 #define dbg(x) cout< 2 #define IO std::ios::sync_with_stdio(0);
3 #include
4 #define iter ::iterator
5 using namespace std;
6 typedef long long ll;
7 typedef pairP;
8 #define pb push_back
9 #define se second
10 #define fi first
11 #define rs o<<1|1
12 #define ls o<<1
13 const ll inf=0x7fffffff;
14 const int N=5e4+10;
15 int l1[N],r1[N],fa[N];
16 ll w[N],t[N];
17 vector<int>g[N];
18 int n,q,cnt;
19 struct node{
20 ll sumv,add;
21 }a[N*4];
22 void dfs(int u){
23 l1[u]=++cnt;
24 t[cnt]=u;
25 for(int i=0;i){
26 int v=g[u][i];
27 if(v==fa[u])continue;
28 dfs(v);
29 }
30 r1[u]=cnt;
31 }
32 void push(int o){
33 a[o].sumv=a[ls].sumv+a[rs].sumv;
34 }
35 void down(int o,int l,int r){
36 if(a[o].add){
37 a[ls].add+=a[o].add;
38 a[rs].add+=a[o].add;
39 int m=(l+r)/2;
40 a[ls].sumv+=1ll*a[o].add*(m-l+1);
41 a[rs].sumv+=1ll*a[o].add*(r-m);
42 a[o].add=0;
43 }
44 }
45 void build(int o,int l,int r){
46 if(l==r){
47 a[o].sumv=w[t[l]];
48 return;
49 }
50 int m=(l+r)/2;
51 build(ls,l,m);
52 build(rs,m+1,r);
53 push(o);
54 }
55 void up(int o,int l,int r,int ql,int qr,ll k){
56 if(l>=ql&&r<=qr){
57 a[o].sumv+=1ll*(r-l+1)*k;
58 a[o].add+=k;
59 return;
60 }
61 down(o,l,r);
62 int m=(l+r)/2;
63 if(ql<=m)up(ls,l,m,ql,qr,k);
64 if(qr>m)up(rs,m+1,r,ql,qr,k);
65 push(o);
66 }
67 ll qu(int o,int l,int r,int ql,int qr){
68 if(l>=ql&&r<=qr){
69 return a[o].sumv;
70 }
71 down(o,l,r);
72 int m=(l+r)/2;
73 ll res=0;
74 if(ql<=m)res+=qu(ls,l,m,ql,qr);
75 if(qr>m)res+=qu(rs,m+1,r,ql,qr);
76 return res;
77 }
78 int main(){
79 scanf("%d%d",&n,&q);
80 for(int i=2;i<=n;i++){
81 scanf("%d%lld",&fa[i],&w[i]);
82 fa[i]++;
83 g[fa[i]].pb(i);
84 }
85 dfs(1);
86 build(1,1,cnt);
87 while(q--){
88 char s[10];
89 scanf("%s",s);
90 ll x,y,z;
91 scanf("%d%lld%lld",&x,&y,&z);
92 x++;
93 if(s[0]=='A'){
94 ll res=qu(1,1,cnt,l1[x],r1[x]);
95 ll h=r1[x]-l1[x]+1;
96 if(res<1ll*y*h){
97 up(1,1,cnt,l1[x],r1[x],z);
98 }
99 }
100 else{
101 ll res=qu(1,1,cnt,l1[x],l1[x]);
102 if(res<y){
103 up(1,1,cnt,l1[x],l1[x],z);
104 }
105 }
106 }
107 for(int i=1;i<=n;i++){
108 printf("%lld
",qu(1,1,cnt,l1[i],l1[i]));
109 }
110 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.