社区讨论

请教一下,为什么把空间翻倍就AC了

EEmplace_back
CF600ELomsat gelral参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo8h48zt
此快照首次捕获于
2023/10/27 18:31
2 年前
此快照最后确认于
2023/10/27 18:31
2 年前
查看原帖
线段树合并做法
把N和M开成两倍就AC了
#25 WA:
CPP
#include<bits/stdc++.h>
#define ll long long
#define fr(i,r) for(int i=1;i<=r;i=-~i)
#define For(i,l,r) for(int i=l;i<=r;i=-~i)
#define Rof(i,r,l) for(int i=r;i>=l;i=~(-i))
#define eb emplace_back
#define pf pop_front
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=1e5+10,M=2e5+10,Inf=0x7fffffff,Mod=998244353;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}
inline void print(int x)
{
	if(x>9) print(x/10);
	putchar(x%10+'0');
}


int n=rd();
int co[N];
int cnt;//nodecnt
struct Tree//对原先的有根树的每一个节点维护一颗以颜色为下标(线段树的区间即为颜色区间)的线段树
{
	int l,r;
	int num;//颜色的出现数目
	ll dat;//答案要求的编号和
}t[N*50];

int fir[N],nex[M],to[M],rot;
inline void link(int s,int t)
{
    nex[++rot]=fir[s];
    fir[s]=rot;
    to[rot]=t;
}

inline void pushup(int u)
{
	int ls=t[u].l,rs=t[u].r;
	if(t[ls].num>t[rs].num) t[u].num=t[ls].num,t[u].dat=t[ls].dat;
	else if(t[ls].num<t[rs].num) t[u].num=t[rs].num,t[u].dat=t[rs].dat;
	else t[u].num=t[ls].num,t[u].dat=t[ls].dat+t[rs].dat;
}

inline int Merge(int a,int b,int l,int r) //将线段树a,b合并到a上
{
	if(!a||!b) return a+b;//若上一层的左右儿子中有节点为空,不用合并,直接返回
	if(l==r) //若搜索到了叶子
	{
		t[a].num+=t[b].num;
		t[a].dat=l;
		return a;
	}
	int mid=l+r>>1;
	t[a].l=Merge(t[a].l,t[b].l,l,mid);
	t[a].r=Merge(t[a].r,t[b].r,mid+1,r);
	pushup(a);
	return a;
}

inline void Add(int &u,int l,int r,int col)
{
	if(!u) u=++cnt;// <!核心1:动态开点> 若不存在节点,新建节点 => 防止定义时一次开满炸空间
	if(l==r)
	{
		++t[u].num;
		t[u].dat=l;//叶子节点只包含这一个点,故直接赋值dat
		return;
	}
	int mid=l+r>>1;
	if(col<=mid) Add(t[u].l,l,mid,col);//若目标颜色在左半段,在左子树继续建树
	else Add(t[u].r,mid+1,r,col);
	pushup(u);
}

inline void Dfs(int u,int fa)//遍历原有根树
{
	for(int e=fir[u];e;e=nex[e])
	{
		int v=to[e];
		if(v^fa)
		{
			Dfs(v,u);
			Merge(u,v,1,n);
		}
	}
	Add(u,1,n,co[u]);//构建以自己为根的线段树
}

int k1,k2;
int main()
{
	//freopen("CF600E.in","r",stdin);
	//freopen("CF600E.out","w",stdout);
	fr(i,n) co[i]=rd();
	//以原树节点编号u作为该节点的线段树的根的节点编号
	cnt=n;//已经对原树的n个节点建起了n颗只有根的线段树,故后续节点从 cnt+1 开始加入
	fr(i,n-1) k1=rd(),k2=rd(),link(k1,k2),link(k2,k1);
	
	Dfs(1,0);
	fr(i,n) print(t[i].dat),putchar(' ');
	
	return 0;
}
这样也WA #25:
CPP
......

const int N=1e5+10,M=2e5+10,Inf=0x7fffffff,Mod=998244353;

......

struct Tree//对原先的有根树的每一个节点维护一颗以颜色为下标(线段树的区间即为颜色区间)的线段树
{
	int l,r;
	int num;//颜色的出现数目
	ll dat;//答案要求的编号和
}t[N*100];

......
AC:
CPP
#include<bits/stdc++.h>
#define ll long long
#define fr(i,r) for(int i=1;i<=r;i=-~i)
#define For(i,l,r) for(int i=l;i<=r;i=-~i)
#define Rof(i,r,l) for(int i=r;i>=l;i=~(-i))
#define eb emplace_back
#define pf pop_front
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=2e5+10,M=4e5+10,Inf=0x7fffffff,Mod=998244353;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}
inline void print(int x)
{
	if(x>9) print(x/10);
	putchar(x%10+'0');
}


int n=rd();
int co[N];
int cnt;//nodecnt
struct Tree//对原先的有根树的每一个节点维护一颗以颜色为下标(线段树的区间即为颜色区间)的线段树
{
	int l,r;
	int num;//颜色的出现数目
	ll dat;//答案要求的编号和
}t[N*50];

int fir[N],nex[M],to[M],rot;
inline void link(int s,int t)
{
    nex[++rot]=fir[s];
    fir[s]=rot;
    to[rot]=t;
}

inline void pushup(int u)
{
	int ls=t[u].l,rs=t[u].r;
	if(t[ls].num>t[rs].num) t[u].num=t[ls].num,t[u].dat=t[ls].dat;
	else if(t[ls].num<t[rs].num) t[u].num=t[rs].num,t[u].dat=t[rs].dat;
	else t[u].num=t[ls].num,t[u].dat=t[ls].dat+t[rs].dat;
}

inline int Merge(int a,int b,int l,int r) //将线段树a,b合并到a上
{
	if(!a||!b) return a+b;//若上一层的左右儿子中有节点为空,不用合并,直接返回
	if(l==r) //若搜索到了叶子
	{
		t[a].num+=t[b].num;
		t[a].dat=l;
		return a;
	}
	int mid=l+r>>1;
	t[a].l=Merge(t[a].l,t[b].l,l,mid);
	t[a].r=Merge(t[a].r,t[b].r,mid+1,r);
	pushup(a);
	return a;
}

inline void Add(int &u,int l,int r,int col)
{
	if(!u) u=++cnt;// <!核心1:动态开点> 若不存在节点,新建节点 => 防止定义时一次开满炸空间
	if(l==r)
	{
		++t[u].num;
		t[u].dat=l;//叶子节点只包含这一个点,故直接赋值dat
		return;
	}
	int mid=l+r>>1;
	if(col<=mid) Add(t[u].l,l,mid,col);//若目标颜色在左半段,在左子树继续建树
	else Add(t[u].r,mid+1,r,col);
	pushup(u);
}

inline void Dfs(int u,int fa)//遍历原有根树
{
	for(int e=fir[u];e;e=nex[e])
	{
		int v=to[e];
		if(v^fa)
		{
			Dfs(v,u);
			Merge(u,v,1,n);
		}
	}
	Add(u,1,n,co[u]);//构建以自己为根的线段树
}

int k1,k2;
int main()
{
	//freopen("CF600E.in","r",stdin);
	//freopen("CF600E.out","w",stdout);
	fr(i,n) co[i]=rd();
	//以原树节点编号u作为该节点的线段树的根的节点编号
	cnt=n;//已经对原树的n个节点建起了n颗只有根的线段树,故后续节点从 cnt+1 开始加入
	fr(i,n-1) k1=rd(),k2=rd(),link(k1,k2),link(k2,k1);
	
	Dfs(1,0);
	fr(i,n) print(t[i].dat),putchar(' ');
	
	return 0;
}
CPP
......

const int N=2e5+10,M=4e5+10,Inf=0x7fffffff,Mod=998244353;

......

struct Tree//对原先的有根树的每一个节点维护一颗以颜色为下标(线段树的区间即为颜色区间)的线段树
{
	int l,r;
	int num;//颜色的出现数目
	ll dat;//答案要求的编号和
}t[N*50];

......

回复

共 2 条回复，欢迎继续交流。

正在加载回复...