听取wa声一片,“C”操作求调
查看原帖
听取wa声一片,“C”操作求调
456924
Amor_S楼主2023/2/20 10:18

样例已过,全wa,和正确代码打对拍,删“C”操作完全相同,但是找不到“C”操作错在哪里……

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>+
using namespace std;
const int N=200005;
int n,m,idx,cnt;
struct node{
	int to,next;
	int w;
}seg[N<<1];
int e[N],ln[N],head[N];
struct Tree{
	int l,r,rev;
	int sum,maxv,minv;
}tr[N<<2];
int id[N],fa[N],nw[N];
int dep[N],top[N],son[N],siz[N];
struct Oper{
	int sum;
	int minv,maxv;
};
void add(int u,int v,int w)
{
	seg[++idx].to=v;
	seg[idx].w=w;
	seg[idx].next=head[u];
	head[u]=idx;
}
void dfs1(int u,int p,int depth,int edge)
{
	siz[u]=1,fa[u]=p,dep[u]=depth,e[u]=edge,ln[edge]=u;
	for(int i=head[u],v;i;i=seg[i].next)
	{
		v=seg[i].to;
		if(v==p)continue;
		dfs1(v,u,depth+1,i);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t,id[u]=++cnt,nw[cnt]=seg[e[u]].w;
	if(!son[u])return;
	dfs2(son[u],t);
	for(int i=head[u],v;i;i=seg[i].next)
	{
		v=seg[i].to;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
inline void pushup(int x)
{
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
	tr[x].minv=min(tr[x<<1].minv,tr[x<<1|1].minv);
	tr[x].maxv=max(tr[x<<1].maxv,tr[x<<1|1].maxv);
}
void build(int u,int l,int r)
{
	tr[u].l=l,tr[u].r=r;
	if(l==r)
	{
		tr[u].sum=nw[l];
		tr[u].maxv=tr[u].minv=nw[r];
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
inline void change(int x,int k)
{
	tr[x].sum=k;
	tr[x].maxv=tr[x].minv=k;
}
inline void change_rev(int u)
{
	tr[u].rev^=1;
	tr[u].sum*=-1;
	swap(tr[u].maxv,tr[u].minv);
	tr[u].maxv*=-1,tr[u].minv*=-1;
}
void pushdown(int u)
{
	if(!tr[u].rev)return;
	tr[u].rev=0;
	change_rev(u<<1);
	change_rev(u<<1|1);
}
void change_pos(int u,int pos,int k)
{
	if(tr[u].l==pos&&tr[u].r==pos)
	{
		change(u,k);
		return;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(pos<=mid)change_pos(u<<1,pos,k);
	else change_pos(u<<1|1,pos,k);
	pushup(u);
}
void update(int u,int l,int r)
{
	if(l>r)return;
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		change_rev(u);
		return;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid)update(u<<1,l,r);
	if(r>mid)update(u<<1|1,l,r);
	pushup(u);
}
void update_path(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		update(1,id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	update(1,id[v]+1,id[u]);
}
Oper operator + (Oper a,Oper b)
{
	a.sum+=b.sum;
	a.maxv=max(a.maxv,b.maxv);
	a.minv=min(a.minv,b.minv);
	return a;
}
void print(Oper a)
{
	printf("%d %d %d\n",a.sum,a.minv,a.maxv);
}
Oper query(int u,int l,int r)
{
	if(l>r)return {0,1000,-1000};
	if(tr[u].l>=l&&tr[u].r<=r)return {tr[u].sum,tr[u].minv,tr[u].maxv};
	pushdown(u);
	Oper opt={0,1000,-1000};
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid)opt=opt+query(u<<1,l,r);
	if(r>mid)opt=opt+query(u<<1|1,l,r);
//	print(opt);
	return opt;
}
Oper query_path(int u,int v)
{
	Oper opt={0,1000,-1000};
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		opt=opt+query(1,id[top[u]],id[u]);
		u=fa[top[u]];
//		cout<<"---------------------------"<<endl;
//		print(opt);
	}
	if(dep[u]<dep[v])swap(u,v);
	opt=opt+query(1,id[v]+1,id[u]);
	return opt;
}
int main()
{
	freopen("1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u+1,v+1,w),add(v+1,u+1,w);
	}
	dfs1(1,0,1,0);
	dfs2(1,1);
	build(1,1,cnt);
	scanf("%d",&m);
	while(m--)
	{
		int x,y;
		char op[5];
		scanf("%s %d%d",op,&x,&y);
		if(*op=='C')change_pos(1,id[ln[x]],y);
		else if(*op=='N')update_path(x+1,y+1);
		else
		{
			Oper opt=query_path(x+1,y+1);
//			cout<<"-------------------------------------------------------------------------------"<<endl;
//			print(opt);
			if(!strcmp(op,"SUM"))printf("%d\n",opt.sum);
			if(!strcmp(op,"MIN"))printf("%d\n",opt.minv);
			if(!strcmp(op,"MAX"))printf("%d\n",opt.maxv);
		}
//		for(int i=1;i<8;i++)printf("%d %d %d %d %d %d %d\n",i,tr[i].l,tr[i].r,tr[i].minv,tr[i].maxv,tr[i].sum,tr[i].rev);
	}
	return 0;
}
2023/2/20 10:18
加载中...