首页 > 代码库 > 51nod1199 Money out of Thin Air
51nod1199 Money out of Thin Air
链剖即可。其实就是利用了链剖后子树都在一段连续的区间内所以可以做到O(logn)查询和修改。
线段树细节打错了。。要专心！肉眼差错都能找出一堆出来显然是不行的！。
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define qwq(x) for(edge *o=head[x];o;o=o->next)#define lson l,mid,x<<1#define rson mid+1,r,x<<1|1#define ll long longint read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=5e4+5;const int inf=0x7f7f7f7f;struct edge{ int to;edge *next;};edge es[nmax<<1],*pt=es,*head[nmax];void add(int u,int v){ pt->to=v;pt->next=head[u];head[u]=pt++; pt->to=u;pt->next=head[v];head[v]=pt++;}int size[nmax],son[nmax],idx[nmax],id[nmax],w[nmax],n,m;ll sm[nmax<<2],col[nmax<<2];void dfs(int x,int fa){ size[x]=1; qwq(x) if(o->to!=fa){ dfs(o->to,x);size[x]+=size[o->to]; if(!son[x]||size[o->to]>size[son[x]]) son[x]=o->to; }}void DFS(int x){ id[++id[0]]=x;idx[x]=id[0]; if(son[x]) DFS(son[x]); qwq(x) if(!idx[o->to]) DFS(o->to);}void build(int l,int r,int x){ col[x]=-1; if(l==r) { sm[x]=w[id[l]];return ; } int mid=(l+r)>>1;build(lson);build(rson);sm[x]=sm[x<<1]+sm[x<<1|1];}void pushdown(int x,int cnt){ if(col[x]!=-1){ if(col[x<<1]!=-1) col[x<<1]+=col[x];else col[x<<1]=col[x]; if(col[x<<1|1]!=-1) col[x<<1|1]+=col[x];else col[x<<1|1]=col[x]; sm[x<<1]+=col[x]*(cnt-(cnt>>1));sm[x<<1|1]+=col[x]*(cnt>>1); col[x]=-1; }}void update(int p,int add,int l,int r,int x){ if(l==r) { sm[x]+=add;return ; } pushdown(x,r-l+1); int mid=(l+r)>>1; p<=mid?update(p,add,lson):update(p,add,rson); sm[x]=sm[x<<1]+sm[x<<1|1];}void Update(int tl,int tr,int add,int l,int r,int x){ if(tl<=l&&tr>=r) { if(col[x]!=-1) col[x]+=add;else col[x]=add; sm[x]+=(ll)add*(r-l+1);return ; } pushdown(x,r-l+1); int mid=(l+r)>>1; if(tl<=mid) Update(tl,tr,add,lson); if(tr>mid) Update(tl,tr,add,rson); sm[x]=sm[x<<1]+sm[x<<1|1];}ll query(int tl,int tr,int l,int r,int x){ if(tl<=l&&tr>=r) return sm[x]; pushdown(x,r-l+1); int mid=(l+r)>>1;ll ans=0; if(tl<=mid) ans+=query(tl,tr,lson); if(tr>mid) ans+=query(tl,tr,rson); return ans;}void UPDATE(int u,int v,int d){ ll sm=query(idx[u],idx[u]+size[u]-1,1,n,1); if(sm>=(ll)v*size[u]) return ; Update(idx[u],idx[u]+size[u]-1,d,1,n,1);}void print(int l,int r,int x){ printf("%d %d %d\n",l,r,sm[x]); if(l==r) return ; int mid=(l+r)>>1; print(lson);print(rson);}ll get(int p,int l,int r,int x){ if(l==r) return sm[x]; pushdown(x,r-l+1); int mid=(l+r)>>1; return p<=mid?get(p,lson):get(p,rson);}char s[5];int main(){ n=read(),m=read();int u,v,d; rep(i,2,n) u=read()+1,w[i]=read(),add(u,i); dfs(1,0);DFS(1);build(1,n,1); //printf("->_->\n");print(1,n,1); rep(i,1,m){ scanf("%s",s);u=read()+1,v=read(),d=read(); if(s[0]==‘S‘) { if(get(idx[u],1,n,1)<v) update(idx[u],d,1,n,1); } else UPDATE(u,v,d); //printf("->_->\n");print(1,n,1); } rep(i,1,n) printf("%lld\n",get(idx[i],1,n,1)); return 0;}
1199 Money out of Thin Air
题目来源： Ural
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注一棵有N个节点的树，每个节点对应1个编号及1个权值，有2种不同的操作。
操作1：S x y z，表示如果编号为x的节点的权值 < y，则将节点x的权值加上z。(Single)
操作2：A x y z，表示如果编号为x的节点以及其所有子节点的权值平均值 < y，则将节点x及其所有子节点的权值加上z。(All)
给出树节点之间的关系，进行M次操作，问所有操作完成后，各个节点的权值为多少？
节点的编号为0 - N - 1，根节点的编号为0，并且初始情况下，根节点的权值也是0。
Input
第1行：2个数N, M，N为节点的数量，M为操作的数量(1 <= N, M <= 50000)。第2 - N行：每行描述一个节点N[i]的信息，第2行对应编号为1的节点，第N行对应编号为N - 1的节点。具体内容为：每行2个数P[i], W[i]。P[i]为当前节点的父节点的编号，W[i]为当前节点的权值。(0 <= W[i] <= 10^5, P[i] < i)第N + 1 - N + M行：每行表示一个操作，N x y z或A x y z，（0 <= y, z <= 10^5)。
Output
输出共N行，每行1个数W[i]，表示经过M次后，编号为0 - N - 1的节点的权值。
Input示例
4 30 100 101 2S 0 1 1A 0 20 1S 3 2 1
Output示例
211113
51nod1199 Money out of Thin Air
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。