20231026

P5537 【XR-3】系统设计 题解-哈希+线段树二分

这个东西怎么会和哈希有关？！直接寄。

Statement

这个系统首先需要输入一棵 \(n\) 个点的有根树和一个长度为 \(m\) 的序列 \(a\)，接下来需要实现 \(q\) 个操作。

操作分两种：

1. 1 x l r 表示设定起点为有根树的节点 \(x\)，接下来依次遍历 \(l \sim r\)。当遍历到 \(i\) 时，从当前节点走向它的编号第 \(a_i\) 小的儿子。如果某一时刻当前节点的儿子个数小于 \(a_i\)，或者已经遍历完 \(l \sim r\)，则在这个点停住，并输出这个点的编号，同时停止遍历。
2. 2 t k 表示将序列中第 \(t\) 个数 \(a_t\) 修改为 \(k\)。

\(1\le n,m,q\le 5 \times 10^5\)。

Solution

看了题之后根本没什么思路，

知道用哈希维护的时候还是没有什么思路。。。

终于用一个小时看懂了这道题，于是写一篇题解。

首先发现题目中的查询一定是走到不能走为止，

那么我们就希望知道这个最远的节点。

因为树的形态是不变的，所以我们从根走到这个节点的路径也是不变的。

也就是说存在唯一的一个序列，表示从根走到节点 \(u\) 的路径，

其中的每一个元素就代表走的第几小的边。

于是我们可以把这个序列变成字符串去维护。

用样例的那棵树理解一下：


我们令序列为 \(s_i\) ，于是在这个图中，有：

举例解释一下：\(s_4=12\) 就表示从根节点 \(1\) 开始走到它第一小的儿子节点 \(2\)，再走 \(2\) 的第二小的儿子节点即可到达 \(4\)。

这样一来，我们就可以用题目中的 \(a\) 数组的表达方式表示出了到每一个节点的位置，而在预处理的时候，我们可以直接维护它的哈希值，从父亲转移到儿子即可。

于是这个序列就和 \(a\) 数组本质相同了。

而按照同样的表达方式，

对于每一次询问，我们把 \(s_x\) 和 \(a_{l\dots r}\) 给合并起来，

这就是理想的序列，

而答案就是在这个序列中能匹配最多的那个节点。

具体来说对于样例里面的第一个询问 1 1 1 3，

把它转化成字符串就是 \(122\)，我们再用 \(s\) 去进行匹配

匹配到最后面的点是 \(s_4=12\)，这就是这次询问的答案。

还是比较好理解。

于是查询的思路有了，那我们怎么实现呢？

不难想到可以用字符串哈希完成询问的比较，

而我们可以用二分答案。

由于还涉及到单点修改，不难想到可以用线段树去维护区间的 \(a\) 。

但是发现如果直接二分会超时，于是可以把二分融入线段树的查询中。

具体来说就是在查询的过程中，

每一次合并两个区间的时候，先考虑左子树的哈希是否有匹配的点，

如果存在就遍历右子树，

反之遍历左子树即可。

具体可以看代码理解。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pll pair<ll,ll>
#define mk make_pair
#define pb push_back

const int N=1e6+5;
int n,m,q,a[N],rt;
vector<int> g[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
} 

void print(int x){
  int p[15],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){p[++tmp]=x%10;x/=10;}
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');putchar('\n');
} 

namespace Hash{
  const int P=1e6-17,s=24601;
  int tot=0,head[N];
  struct node{
  	pll val;
  	int nxt,w;
  }e[N];//链式前向星去存储哈希以完成比较
  void add(int u,pll val,int w){
  	e[++tot]=(node){val,head[u],w};
  	head[u]=tot;
  }
  void ins(pll a,int id){
  	int tmp=(a.fi*s+a.se)%P;
  	add(tmp,a,id);
  } 
  int qry(pll a){
  	int tmp=(a.fi*s+a.se)%P;
  	for(int i=head[tmp];i;i=e[i].nxt)
  	  if(e[i].val==a) return e[i].w;
  	return -1;
  }
}

pll ph[N],hs[N];//双哈希数组，维护每一个点的s
const pll base={114514,1919810},mod={1e9+7,998244353}; 

pll operator +(const pll &a,const pll &b){return {(a.fi+b.fi)%mod.fi,(a.se+b.se)%mod.se};}
pll operator *(const pll &a,const pll &b){return {(a.fi*b.fi)%mod.fi,(a.se*b.se)%mod.se};}

void init(){
  ph[0]=mk(1,1);
  for(int i=1;i<=n;i++) ph[i]=ph[i-1]*base;
}

void dfs(int u){
  sort(g[u].begin(),g[u].end());
  int cnt=0;
  for(auto v:g[u]){
  	cnt++;
  	hs[v]=hs[u]*base+mk(cnt,cnt);
    dfs(v);
  }
}

#define mid ((l+r)>>1)
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define lc p<<1
#define rc p<<1|1
pll tr[N<<2];
  
void pu(int l,int r,int p){tr[p]=(tr[lc]*ph[r-mid]+tr[rc]);}
void build(int l,int r,int p){
  if(l==r){
  	tr[p]={1ll*a[l],1ll*a[l]};
	return;	
  }
  build(lson);build(rson);
  pu(l,r,p);
}

void update(int l,int r,int p,int x,ll val){
  if(l==r){
  	tr[p]={val,val};
	return;	
  }
  if(x<=mid) update(lson,x,val);
  else update(rson,x,val);
  pu(l,r,p);
}

pll query(int l,int r,int p,int x,int y){
  if(x<=l&&y>=r) return tr[p];
  if(y<=mid) return query(lson,x,y);
  if(x>mid) return query(rson,x,y);
  return query(lson,x,y)*ph[min(r,y)-mid]+query(rson,x,y);
}

int ask(int l,int r,int p,int x,int y,pll val){
  if(l==r) return Hash::qry(val*base+tr[p]); 
  if(y<=mid) return ask(lson,x,y,val);
  if(x>mid) return ask(rson,x,y,val);
  pll h=val*ph[mid-max(l,x)+1]+((x>l)?query(l,r,p,x,mid):tr[lc]);
  int tmp=Hash::qry(h);
  if(tmp==-1) return ask(lson,x,y,val);
  else {
  	int res=ask(rson,x,y,h);
	return (res!=-1)?res:tmp;	
  }
}

int main(){
  freopen("P5537.in","r",stdin);
  freopen("P5537.out","w",stdout);
  /*2023.10.26 H_W_Y P5537 【XR-3】系统设计 Hash+线段树二分*/ 
  n=read();m=read();q=read();
  init();
  for(int i=1;i<=n;i++){
  	int x=read();
  	if(x) g[x].pb(i);
    else rt=i;
  }
  hs[rt]=mk(0,0);dfs(rt);
  for(int i=1;i<=n;i++) Hash::ins(hs[i],i);
  for(int i=1;i<=m;i++) a[i]=read();
  build(1,m,1);
  for(int i=1;i<=q;i++){
  	int op=read();
  	if(op==1){
  	  int x=read(),l=read(),r=read();
	  int tmp=ask(1,m,1,l,r,hs[x]);
	  print((tmp==-1)?x:tmp);	
	}
	else {
	  int x=read(),val=read();
	  update(1,m,1,x,val);
	}
  }
  return 0;
}

Conclusion

树上的路径走法问题我们可以用字符串维护，再用哈希比较。