P5537 【XR-3】系统设计(线段树上二分+哈希)
P5537 【XR-3】系统设计
这题真是一道神仙毒瘤题啊!
谁能想得到这玩意能Hash。。。
感谢并orz同校巨佬 zyt1253679098 和他的博客
-
因为树是不修改的，所以任意一对祖先 - 后代之间的路径都可以按题目所述的规则表示成一个固定的整数序列，并且这个序列是可以合并的，即如果
u 是v 的祖先，v 是w 的祖先，则(u,v) 的序列与(v,w) 的序列拼接起来就是(u,w) 的序列。 -
这样，我们就可以用一个序列（对应着从根到这个结点的走法）来表示一个结点了。 我们在dfs过程中按编号给子节点排序，预处理出从父节点到子节点的数字序列， 把序列 - 结点的映射关系用哈希表存下来，就可以
O(1) 判断从一个结点按照一个序列走若干步能否走到一个结点，以及查询如果能走到，走到的是哪个结点。 -
最终做法： 预处理出每个结点序列的哈希值，并用线段树维护给定序列的哈希值。查询时在线段树上二分走的长度（即取序列
[l,mid] 的部分），判断能否走到一个结点。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define mkp make_pair
using namespace std;
namespace FGF
{
int n,m,Q,rt;
const int N=1e6+5;
const pii seed=mkp(71,853),mo=mkp(1e9+7,1e9+9);
int read()
{
int s=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
return s;
}
pii operator + (const pii &a,const pii &b)
{
return mkp((a.first+b.first)%mo.first,(a.second+b.second)%mo.second);
}
pii operator * (const pii &a,const pii &b)
{
return mkp((a.first*b.first)%mo.first,(a.second*b.second)%mo.second);
}
pii po[N],h[N];
void init()
{
po[0]=mkp(1,1);
for(int i=1;i<=n;i++)
po[i]=po[i-1]*seed;
}
struct edg{
pii to;int w,nxt;
}e[N];
int head[N],cnt;
const int se=24601,p=1e6-17;
struct HashTable{
void add(const int a,const pii b,const int c)
{
cnt++;
e[cnt].to=b,e[cnt].w=c,e[cnt].nxt=head[a],head[a]=cnt;
}
void inser(const pii a,const int b)
{
int tmp=(a.first*se+a.second)%p;
add(tmp,a,b);
}
int query(pii a)
{
int tmp=(a.first*se+a.second)%p;
for(int i=head[tmp];i;i=e[i].nxt)
if(e[i].to==a)return e[i].w;
return -1;
}
}Ha;
int a[N];
struct tree{
int l,r;pii val;
}t[N<<2];
void pushup(int ro,int len)
{
t[ro].val=t[ro<<1].val*po[len]+t[ro<<1|1].val;
}
void build(int ro,int l,int r)
{
t[ro].l=l,t[ro].r=r;
if(l==r)
{
t[ro].val=mkp(a[l],a[l]);
return;
}
int mid=(l+r)>>1;
build(ro<<1,l,mid),build(ro<<1|1,mid+1,r);
pushup(ro,t[ro].r-mid);
}
void updat(int ro,int pos,int x)
{
if(t[ro].l==t[ro].r)
{
t[ro].val=mkp(x,x);
return;
}
int mid=(t[ro].l+t[ro].r)>>1;
pos<=mid? updat(ro<<1,pos,x):updat(ro<<1|1,pos,x);
pushup(ro,t[ro].r-mid);
}
pii query(int ro,int l,int r)//查询区间哈希值
{
if(l<=t[ro].l&&t[ro].r<=r)return t[ro].val;
int mid=(t[ro].l+t[ro].r)>>1;
if(r<=mid)return query(ro<<1,l,r);
else if(l>mid)return query(ro<<1|1,l,r);
else return query(ro<<1,l,r)*po[min(r,t[ro].r)-mid]+query(ro<<1|1,l,r);
}
int askk(int ro,int l,int r,pii x)//在线段树上二分
{
if(t[ro].l==t[ro].r)return Ha.query(x*seed+t[ro].val);
int mid=(t[ro].l+t[ro].r)>>1;
if(r<=mid)return askk(ro<<1,l,r,x);
else if(l>mid)return askk(ro<<1|1,l,r,x);
else
{
pii hh=x*po[mid-max(t[ro].l,l)+1]+(l<=t[ro].l? t[ro<<1].val:query(ro,l,mid));
int w=Ha.query(hh);//检查能否走[l,mid]这一段区间
if(w==-1)return askk(ro<<1,l,r,x);//不能就继续在左区间二分
else //可以就查询右区间
{
int tmp=askk(ro<<1|1,l,r,hh);
return tmp==-1? w:tmp;
}
}
}
vector<int> g[N];
void dfs(int u)//预处理出到每个点的数字序列的哈希值
{
sort(g[u].begin(),g[u].end());
int cnt=0;
for(int sz=g[u].size(),i=0;i<sz;i++)
{
int v=g[u][i];
++cnt;
h[v]=h[u]*seed+mkp(cnt,cnt);
dfs(v);
}
}
void work()
{
n=read(),m=read(),Q=read();
init();
for(int i=1;i<=n;i++)
{
int x=read();
if(!x)rt=i;
else g[x].push_back(i);
}
h[rt]=mkp(0,0);
dfs(rt);
for(int i=1;i<=n;i++)//把每个点和其数字序列的对应关系放到哈希表里
Ha.inser(h[i],i);
for(int i=1;i<=m;i++)
a[i]=read();
build(1,1,m);//线段树维护给定序列的哈希值
int op,x,l,r,ans;
while(Q--)
{
op=read();
if(op==1)
{
x=read(),l=read(),r=read();
ans=askk(1,l,r,h[x]);
printf("%d\n",ans==-1? x:ans);
}
else
{
l=read(),x=read();
updat(1,l,x);
}
}
}
}
int main()
{
FGF::work();
return 0;
}