CF840E In a Trap

一、题目

点此看题

二、解法

感冒在家两天，今天才回学校，虽然博客鸽了一天但是我换签名了。

对于询问其实可以分块，每一块的前 \(8\) 位都是一样的，那么处理后 \(8\) 位就可以了，设 \(f(u,i)\) 表示 \(u\) 向上的 \(256\) 个节点中，最大的 \(a_v\oplus (dep_u-dep_v)\oplus (i\cdot 256)\)，那么查询可以先跳整块再跳散块。

对于上面这东西显然可以值域分治，对于前 \(8\) 位我们可以搞一个 \(\tt trie\) 树直接查询。对于后 \(8\) 位我们开一个桶 \(g(u,i)\) 表示前 \(8\) 位为 \(i\) 的 \(a_v\)，最大的 \(((dep_u-dep_v)\oplus a_v)\and 256\)，那么 \(f(u,i)\) 就可以通过这两者拼凑出来。

预处理的复杂度是 \(O(n\log n\sqrt n)\)，询问的复杂度是 \(O(q\sqrt n)\)

三、总结

看到 \(a_i\leq n\) 之类的限制多半要用到值域分块，对于加法和异或的混合问题可以考虑对半拆位。

#include 
#include 
#include 
using namespace std;
const int M = 50005;
const int N = 256;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,a[M],fa[M],dep[M],f[M][260],mx[M][260];
vector g[M];int cnt,ch[M][2],lst[M];
void upd(int &x,int y) {x=max(x,y);}
void ins(int x)
{
	for(int i=7,p=1;i>=0;i--)
	{
		int w=(x>>i)&1;
		if(!ch[p][w]) ch[p][w]=++cnt;
		p=ch[p][w];
	}
}
int ask(int x,int u)
{
	int v=0,res=0;
	for(int i=7,p=1;i>=0;i--)
	{
		int w=((x>>i)&1)^1;
		if(ch[p][w]) p=ch[p][w],res|=(1<=N)
	{
		for(int i=1;i<=cnt;i++) ch[i][0]=ch[i][1]=0;
		cnt=1;int i=u;
		for(;dep[u]-dep[i]>8],(dep[u]-dep[i]^a[i])&255);
			ins(a[i]>>8);
		}
		lst[u]=i;
		for(i=0;i=N;v=lst[v],d++) ans=max(ans,f[v][d]);
		for(d<<=8;v!=fa[u];v=fa[v],d++) ans=max(ans,d^a[v]);
		printf("%d\n",ans);
	}
}