1 条题解

  • 0
    @ 2025-8-24 22:16:46

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar zhengrunzhe
    为世界上所有的美好而战

    搬运于2025-08-24 22:16:46，当前版本为作者最后更新于2020-02-03 13:24:35，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    毒瘤出题人卡时空

    题意：给定一棵带点权树，求树中有多少对(u,v)满足v在u的子树中且orsum(path(u,v))>=k

    首先orsumorsum满足结合律和单调性，不妨考虑枚举每个vv有多少个祖先满足条件，当某个祖先u满足orsum≥korsum\geq k的时候，u的所有祖先也都满足orsum≥korsum\geq k

    考虑倍增从v跳到最深的满足orsum≥korsum\geq k的祖先u，那么对答案产生的贡献就是dep[u]dep[u](dep[root]=1dep[root]=1)

    预处理anc[i][j]anc[i][j]表示ii的2j2^j祖先，和orsum[i][j]orsum[i][j]表示ii的父亲到ii的2j2^j祖先路径点权或和，dfsdfs一遍预处理出每个点的深度dep[i]dep[i]

    然后倍增就是基础操作了

    #include<cstdio>
template<class type>inline const void read(type &in)
{
	in=0;char ch(getchar());
	while (ch<48||ch>57)ch=getchar();
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+10),logn(20);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N];
inline const void addedge(const int &u,const int &v)
{
	next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
	for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
	for (int j(1);j<=logn;j++)
		for (int i(1);i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1],
			orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
	int sum(val[p]);
	if (sum>=k)return p;
	for (int i(logn);~i;i--)
		if (anc[p][i])
			if ((sum|orsum[p][i])<k)
				sum|=orsum[p][i],p=anc[p][i];
	return anc[p][0];
}
int main()
{
	read(n);read(k);
	for (int i(1);i<=n;i++)read(val[i]);
	for (int u,v,i(1);i<n;i++)read(u),read(v),addedge(u,v),orsum[v][0]=val[anc[v][0]=u];
	for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
	for (int i(1);i<=n;i++)ans+=dep[jump(i)];
	printf("%lld\n",ans);
	return 0;
}

    然后交一发mle70分，发现subtask4给了256mb可以过，subtask2都是一百万的链只给128mb就被卡了

    然后此时来思考一下链怎么做

    这个链非常友好，是形如$1\rightarrow 2\rightarrow 3\rightarrow \cdots \rightarrow n$的链，考虑链转序列，编号几就是第几个数

    同样的思路我们可以对每个ii找到编号j≤ij\leq i且orsum[j,i]≤korsum[j,i]\leq k的最小jj，不能再倍增了一开106∗2010^6*20的数组直接mle

    考虑把倍增换成二分，只要我们能够获取区间orsumorsum就能实现

    由于orsumorsum没有可减性，我们不能够通过前缀和的方式O(1)O(1)获取

    一种简单的方法通过线段树维护O(log⁡n)O(\log n)获取

    然后外面套个二分合起来就是O(nlog⁡2n)O(n\log^2 n)的

    考虑能不能在线段树上二分，显然是可以做的，但是不太好理解，我就写了个SplaySplay上二分

    #include<cstdio>
template<class type>inline const void read(type &in)
{
	in=0;char ch(getchar());
	while (ch<48||ch>57)ch=getchar();
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+1),logn(19);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N],u[N],v[N];
inline const void addedge(const int &u,const int &v)
{
	next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
	for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
	for (int j(1);j<=logn;j++)
		for (int i(1);i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1],
			orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
	int sum(val[p]);
	if (sum>=k)return p;
	for (int i(logn);~i;i--)
		if (anc[p][i])
			if ((sum|orsum[p][i])<k)
				sum|=orsum[p][i],p=anc[p][i];
	return anc[p][0];
}
namespace Splay
{
	struct tree
	{
		int orsum,val;
		tree *son[2],*fa;
		static tree *null;
		void *operator new[](size_t size);
		inline tree():orsum(0),val(0)
		{
			static bool init(0);
			if (!init)
				init=1,
				null=new tree,
				null->son[0]=null->son[1]=null->fa=null;
			son[0]=son[1]=fa=null;
		}
		inline const void pushup()
		{
			orsum=son[0]->orsum|val|son[1]->orsum;
		}
		inline const void set(tree *p,const bool &f)
		{
			if (p!=null)p->fa=this;
			if (this!=null)son[f]=p;
		}
		inline const bool id()
		{
			return fa->son[1]==this;
		}
		inline const void rotate()
		{
			const bool f(id());
			tree *fa(this->fa);
			fa->fa->set(this,fa->id());
			fa->set(son[f^1],f);
			set(fa,f^1);
			fa->pushup();pushup();
		}
		inline const void splay()
		{
			for (;fa!=null;rotate())
				if (fa->fa!=null)
					(fa->id()^id()?this:fa)->rotate();
		}
	}*node0,*tree::null;
	#define null tree::null
	inline tree *node(const int &x){return node0+x;}
	char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
	inline void *tree::operator new[](size_t size){return tail-=size;}
	inline tree *build(const int &l,const int &r,tree *fa)
	{
		if (l>r)return null;
		const int mid(l+r>>1);
		node(mid)->val=val[mid];node(mid)->fa=fa;
		if (l==r)return node(l)->orsum=node(l)->val,node(l);
		node(mid)->son[0]=build(l,mid-1,node(mid));
		node(mid)->son[1]=build(mid+1,r,node(mid));
		node(mid)->pushup();
		return node(mid);
	}
	inline const int query(const int &pos)
	{
		tree *p(node(pos));
		p->splay();
		if (p->val>=k)return pos;
		int sum(p->val);p=p->son[0];
		while (p!=null)
			if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
			else if ((sum|p->son[1]->orsum|p->val)>=k)return p-node0;
				else sum|=p->son[1]->orsum|p->val,p=p->son[0];
		return 0;
	}
}using namespace Splay;
int main()
{
	read(n);read(k);
	for (int i(1);i<=n;i++)read(val[i]);
	bool type(1);
	for (int i(1);i<n;i++)read(u[i]),read(v[i]),type=type&&v[i]==u[i]+1;
	if (type)
	{
		node0=new tree[n+1];
		build(1,n,null);
		for (int i(1);i<=n;i++)ans+=query(i);
		printf("%lld\n",ans);
		return 0;
	}
	for (int i(1);i<n;i++)addedge(u[i],v[i]),orsum[v[i]][0]=val[anc[v[i]][0]=u[i]];
	for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
	for (int i(1);i<=n;i++)ans+=dep[jump(i)];
	printf("%lld\n",ans);
	return 0;
}

    能往右儿子走就往右儿子走，否则看看自己满不满足条件，满足就是自己，否则往左儿子走，记一个排名在当前节点之后的点权或和，往左儿子走的时候就把右子树或和与当前点权的或和累计起来

    然后我一开始是这样先把树建好然后把每个点都splaysplay到根，先判断根自己是不是满足条件，否则在其左子树上执行上述二分过程

    然后这个玩意tle了四个点，因为建树完之后每次查询树中的点数都是nn的，这个常数就大了

    因为每次查询之和其前面的数有关，我们不妨一个个插入一个个查

    考虑现在原来的平衡树上查，把前一个点splaysplay执行二分，查完之后把这个点插入到根的右儿子上

    这样子做的复杂度实际上是错的，这样子出来的树形态是一条链，那就完蛋了

    需要多splasplay几个点维持平衡结构

    inline const void query(const int &pos)
{
	if (pos==1)return ans+=val[pos]>=k,void();
	tree *p(node(pos-1));p->splay();
	p->set(node(pos),1);p->orsum|=val[pos];
	int sum(0);
	while (p!=null)
		if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
		else if ((sum|=(p->son[1]->orsum|p->val))>=k)break;
			else p=p->son[0];
	if (p!=null)ans+=p-node0;
	p->splay();
}

    接着我写了个这个玩意，把二分到的答案点splaysplay到根，由于答案点十分的随机，所以整个树也许比较随机平衡，然而它还是t了一个点

    到最后我实在是懒得想了，直接随机找一个点splaysplay:

    #include<cstdio>
#include<cstdlib>
template<class type>inline const void read(type &in)
{
	in=0;char ch(getchar());
	while (ch<48||ch>57)ch=getchar();
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+1),logn(19);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N],u[N],v[N];
inline const void addedge(const int &u,const int &v)
{
	next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
	for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
	for (int j(1);j<=logn;j++)
		for (int i(1);i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1],
			orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
	int sum(val[p]);
	if (sum>=k)return p;
	for (int i(logn);~i;i--)
		if (anc[p][i])
			if ((sum|orsum[p][i])<k)
				sum|=orsum[p][i],p=anc[p][i];
	return anc[p][0];
}
namespace Splay
{
	struct tree
	{
		int orsum,val;
		tree *son[2],*fa;
		static tree *null;
		void *operator new[](size_t size);
		inline tree():orsum(0),val(0)
		{
			static bool init(0);
			if (!init)
				init=1,
				null=new tree,
				null->son[0]=null->son[1]=null->fa=null;
			son[0]=son[1]=fa=null;
		}
		inline const void pushup()
		{
			orsum=son[0]->orsum|val|son[1]->orsum;
		}
		inline const void set(tree *p,const bool &f)
		{
			if (p!=null)p->fa=this;if (this!=null)son[f]=p;
		}
		inline const bool id()
		{
			return fa->son[1]==this;
		}
		inline const void rotate()
		{
			const bool f(id());
			tree *fa(this->fa);
			fa->fa->set(this,fa->id());
			fa->set(son[f^1],f);
			set(fa,f^1);
			fa->pushup();pushup();
		}
		inline const void splay()
		{
			for (;fa!=null;rotate())
				if (fa->fa!=null)
					(fa->id()^id()?this:fa)->rotate();
		}
	}*node0,*tree::null;
	#define null tree::null
	inline tree *node(const int &x){return node0+x;}
	char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
	inline void *tree::operator new[](size_t size){return tail-=size;}
	inline const void query(const int &pos)
	{
		if (pos==1)return ans+=val[pos]>=k,void();
		tree *p(node(pos-1));p->splay();
		p->set(node(pos),1);p->orsum|=val[pos];
		if (val[pos]>=k)return ans+=pos,void();
		if ((val[pos]|val[pos-1])>=k)return ans+=pos-1,void();
		int sum(0);
		while (p!=null)
			if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
			else if ((sum|=(p->son[1]->orsum|p->val))>=k)break;
				else p=p->son[0];
		if (p!=null)ans+=p-node0;
		node(rand()%pos+1)->splay(); //鬼才操作
	}
}using namespace Splay;
int main()
{
	srand(19260817);
	read(n);read(k);
	for (int i(1);i<=n;i++)read(val[i]);
	bool type(1);
	for (int i(1);i<n;i++)read(u[i]),read(v[i]),type=type&&v[i]==u[i]+1;
	if (type)
	{
		node0=new tree[n+1];
		for (int i(1);i<=n;i++)node(i)->val=node(i)->orsum=val[i];
		for (int i(1);i<=n;i++)query(i);
		printf("%lld\n",ans);
		return 0;
	}
	for (int i(1);i<n;i++)addedge(u[i],v[i]),orsum[v[i]][0]=val[anc[v[i]][0]=u[i]];
	for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
	for (int i(1);i<=n;i++)ans+=dep[jump(i)];
	printf("%lld\n",ans);
	return 0;
}

    然后这个玩意它居然A了，全 体 起 立

    • 1

    「ACOI2020」惊吓路径

    信息

    ID
    4934
    时间
    1000ms
    内存
    128~256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 25ms