迷惑行为
查看原帖
迷惑行为
177070
暗ざ之殇楼主2020/9/22 17:36

调代码过程中,蒟蒻在每次循环后输出了每个点的值,发现如果每次操作后查询一下每个点的值(注释里的代码)的话答案就是正确的,但不查询答案就不对,可以把注释去掉再跑一遍会发现结果不一样,能问问这是为啥吗?

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
	ll a=0,x=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') x=-x;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		a=(a<<1)+(a<<3)+(ch^48);
		ch=getchar();
	}
	return a*x;
}
const int N=4e5;
int n,tim,Edge;
int head[N],val[N],dfn[N],dep[N],size[N],Id[N],Fa[N],top[N],son[N];
int sum[N<<2],lazy1[N<<2],lazy2[N<<2];
char opt[10];
struct node
{
	int from,to,nxt,dis;
}a[N<<1];
void add(int from,int to,int dis)
{
	Edge++;
	a[Edge].from=from;
	a[Edge].to=to;
	a[Edge].dis=dis;
	a[Edge].nxt=head[from];
    head[from]=Edge;
}
void dfs1(int u,int fa)
{
	dep[u]=dep[fa]+1;
	size[u]=1;
	for(int i=head[u];i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==fa) continue;
		val[v]=a[i].dis;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]]) son[u]=v;
		Fa[v]=u;
	}
}
void dfs2(int u,int fa)
{
	if(u==0) return ;
	dfn[u]=++tim;
	Id[tim]=u;
	if(u==son[fa]) top[u]=top[fa];
	else top[u]=u;
	dfs2(son[u],u);
	for(int i=head[u];i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==fa||v==son[u]) continue;
		dfs2(v,u);
	}
}
void update(int node)
{
	sum[node]=max(sum[node<<1],sum[node<<1|1]);
}
void build(int node,int l,int r)
{
	lazy1[node]=lazy2[node]=-1;
	if(l==r)
	{	
		sum[node]=val[Id[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
	update(node);
	//printf("%d %d %d???\n",l,r,sum[node]);
}
void pushdown(int node,int l,int r)
{
	int mid=(l+r)>>1;
	if(lazy1[node]!=-1)
	{
		lazy1[node<<1]=lazy1[node];
		lazy1[node<<1|1]=lazy1[node];
		sum[node<<1]=lazy1[node];
		sum[node<<1|1]=lazy1[node];
		lazy1[node]=lazy2[node]=-1;
	}
	if(lazy2[node]!=-1)
	{
		lazy2[node<<1]+=lazy2[node]+(lazy2[node<<1]==-1);
		lazy2[node<<1|1]+=lazy2[node]+(lazy2[node<<1|1]==-1);
		sum[node<<1]+=lazy2[node];
		sum[node<<1|1]+=lazy2[node];
		lazy2[node]=-1;
	}
}
void insert1(int node,int l,int r,int x,int y,int k)
{
	if(x<=l&&r<=y)
	{
		sum[node]=k;
		lazy1[node]=k;
		lazy2[node]=-1;
		return ;
	}
	pushdown(node,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) insert1(node<<1,l,mid,x,y,k);
	if(y>mid) insert1(node<<1|1,mid+1,r,x,y,k);
	update(node);
}
void insert2(int node,int l,int r,int x,int y,int k)
{
	if(x<=l&&r<=y)
	{
		sum[node]+=k;
		if(lazy1[node]!=-1) lazy1[node]=+k;
		lazy2[node]+=k+(lazy2[node]==-1);
		return ;
	}
	pushdown(node,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) insert2(node<<1,l,mid,x,y,k);
	if(y>mid) insert2(node<<1|1,mid+1,r,x,y,k);
	update(node);
}
int query(int node,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) return sum[node];
	pushdown(node,l,r);
	int mid=(l+r)>>1;
	int cnt=0;
	if(x<=mid) cnt=max(cnt,query(node<<1,l,mid,x,y));
	if(y>mid) cnt=max(cnt,query(node<<1|1,mid+1,r,x,y));
	return cnt;
}
void Cover(int u,int v,int w)
{
	if(u==v) return;
	while(top[u]!=top[v])
    {
    	int tu=top[u];
    	int tv=top[v];
    	if(dep[tu]>dep[tv])
    	{
    		insert1(1,1,n,dfn[tu],dfn[u],w);
    		u=Fa[tu];
		}
		else
		{
			insert1(1,1,n,dfn[tv],dfn[v],w);
			v=Fa[tv];
		}
	}
	if(dep[u]<dep[v]) swap(u,v);
	insert1(1,1,n,dfn[son[v]],dfn[u],w);
}
void Add(int u,int v,int w)
{
	if(u==v) return ;
	while(top[u]!=top[v])
    {
    	int tu=top[u];
    	int tv=top[v];
    	if(dep[tu]>dep[tv])
    	{
    		insert2(1,1,n,dfn[tu],dfn[u],w);
    		u=Fa[tu];
		}
		else
		{
			insert2(1,1,n,dfn[tv],dfn[v],w);
			v=Fa[tv];
		}
	}
	if(dep[u]<dep[v]) swap(u,v);
	insert2(1,1,n,dfn[son[v]],dfn[u],w);
}
int Max(int u,int v)
{
	int cnt=0;
	if(u==v) return cnt;
	while(top[u]!=top[v])
    {
    	int tu=top[u];
    	int tv=top[v];
    	if(dep[tu]>dep[tv])
    	{
    		cnt=max(cnt,query(1,1,n,dfn[tu],dfn[u]));
    		u=Fa[tu];
		}
		else 
		{
			cnt=max(cnt,query(1,1,n,dfn[tv],dfn[v]));
			v=Fa[tv];
		}
	}
	if(dep[u]<dep[v]) swap(u,v);
	cnt=max(cnt,query(1,1,n,dfn[son[v]],dfn[u]));
	return cnt;
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
    {
    	int u=read();
    	int v=read();
    	int w=read();
    	add(u,v,w);
    	add(v,u,w);
	}
	dfs1(1,0);dfs2(1,0);
	build(1,1,n);
	while(cin>>opt)
	{
		if(opt[1]=='t') break;
		if(opt[1]=='h')
		{
			int x=read();int y=read();
			int u=a[x<<1].from;int v=a[x<<1].to;
			if(dep[u]>dep[v]) insert1(1,1,n,dfn[u],dfn[u],y);
			else insert1(1,1,n,dfn[v],dfn[v],y);
		}
		if(opt[1]=='o')
		{
			int u=read();
			int v=read();
			int w=read();
			Cover(u,v,w);
		}
		if(opt[1]=='d')
		{
			int u=read();
			int v=read();
			int w=read();
			Add(u,v,w);
		}
		if(opt[1]=='a')
		{
			int u=read();
			int v=read();
			printf("%d\n",Max(u,v));
		}
		/*for(int i=1;i<=n;i++)
		    query(1,1,n,dfn[i],dfn[i]);*/	   
	}
	return 0;
}
15
1 10 19
2 9 39
3 12 3
4 12 21
5 1 23
6 5 91
7 10 80
8 1 93
9 4 50
10 9 41
11 4 66
13 5 85
14 15 50
15 2 54
Add 15 11 72
Add 5 9 64
Add 13 1 57
Max 8 7
Max 1 8
Add 1 8 44
Change 14 25
Change 11 33
Cover 6 12 45
Add 13 12 92
Cover 4 4 48
Add 10 3 55
Add 2 10 26
Change 13 34
Add 9 1 43
Cover 15 2 3
Cover 3 2 51
Max 10 14
Change 10 81
Cover 10 6 89
Stop

附加一组数据,上面的代码输出:

93
93
124

但如果把注释去掉,输出(正确结果):

93
93
261
2020/9/22 17:36
加载中...