首页 > 代码库 > 51nod1199 Money out of Thin Air

51nod1199 Money out of Thin Air

2024-08-13 11:04:58   218人阅读

链剖即可。其实就是利用了链剖后子树都在一段连续的区间内所以可以做到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


联系
我们