小睿睿的兄弟

C++ 解法, 执行用时: 3470ms, 内存消耗: 521180K, 提交时间: 2021-10-12 20:35:35

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
typedef pair<int,int> P;
const int maxn=1e6+5;

int a[maxn],b[maxn],fa[maxn][21],n,m,u,v,now,md,ans,pt;
int dfn[maxn],rnk[maxn],dep[maxn],sz[maxn],lst[maxn];
int rt[maxn],ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],cnt;
vector<int>ed[maxn],rk[maxn];

void build(int&t,int l,int r)
{
	t=++cnt;
	if(l==r)return;
	int mid=l+r>>1;
	build(ls[t],l,mid);
	build(rs[t],mid+1,r);
	return;
}

int update(int o,int l,int r,int pos)
{
	int t=++cnt;
	ls[t]=ls[o],rs[t]=rs[o],sum[t]=sum[o]+1;
	if(l==r)return t;
	int mid=l+r>>1;
	if(pos<=mid)ls[t]=update(ls[o],l,mid,pos);
	else rs[t]=update(rs[o],mid+1,r,pos);
	return t;
}

int query(int u,int v,int l,int r,int k)
{
	if(l==r)return b[l];
	int num=sum[ls[v]]-sum[ls[u]];
	int mid=l+r>>1;
	if(num>=k)return query(ls[u],ls[v],l,mid,k);
	else return query(rs[u],rs[v],mid+1,r,k-num);
}

void dfs(int x,int f)
{
	dep[x]=dep[f]+1,fa[x][0]=f,md=max(md,dep[x]);
	dfn[x]=++now,rnk[now]=x,sz[x]=1;
	for(int i=1;i<=20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(auto y:ed[x])
		if(y!=f)dfs(y,x),sz[x]+=sz[y];
	return;
} 

int getf(int x,int k)
{
	for(int i=20;i>=0;i--)
	{
		if(k>=(1<<i))
		{
			x=fa[x][i];
			k-=1<<i;
		}
	}
	return x;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m; 
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	dfs(1,0); sort(b+1,b+1+n);
	pt=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+pt,a[i])-b;
	build(rt[0],1,pt);
	for(int i=1;i<=n;i++)
	{
		int p=rnk[i],pl=lst[dep[p]]; 
		rt[i]=update(rt[pl],1,pt,a[p]);
		rk[dep[p]].push_back(i);
		lst[dep[p]]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		u=(u^ans)%n+1;
		int f=getf(u,v),dpu=dep[u];
		if(!f){cout<<"?\n"; continue;}
		int l=dfn[f],r=dfn[f]+sz[f]-1;
		int l1=lower_bound(rk[dpu].begin(),rk[dpu].end(),l)-rk[dpu].begin();
		int r1=upper_bound(rk[dpu].begin(),rk[dpu].end(),r)-rk[dpu].begin()-1;
		if(r1<l1)cout<<"?\n";
		else
		{
			int l2=l1?rk[dpu][l1-1]:0,r2=rk[dpu][r1];
			if(sum[rt[r2]]-sum[rt[l2]]<v)cout<<"?\n";
			else cout<<(ans=query(rt[l2],rt[r2],1,pt,v))<<"\n";
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 2016ms, 内存消耗: 506104K, 提交时间: 2020-09-15 16:16:55

#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int M=1e6+1;
int ls[M*22],rs[M*22],cnt[M*22];
int n,m,tot,dfs_tot;
int dep[M],f[M][20],L[M],R[M],A[M],pos[M],tree[M],clo[M];
vector <int> edge[M],v[M];
void insert(int ot,int &rt,int l,int r,int p){
	rt=++tot;
	ls[rt]=ls[ot],rs[rt]=rs[ot],cnt[rt]=cnt[ot]+1;
	if(l==r)return ;
	int mid=l+r>>1;
	if(p<=mid)insert(ls[ot],ls[rt],l,mid,p);
	else insert(rs[ot],rs[rt],mid+1,r,p);
}
int query(int lt,int rt,int l,int r,int k){
	if(l==r)return l;
	int c=cnt[ls[rt]]-cnt[ls[lt]],mid=l+r>>1;
	if(c>=k)return query(ls[lt],ls[rt],l,mid,k);
	else return query(rs[lt],rs[rt],mid+1,r,k-c);
}

void dfs(int x,int fa){
	dep[x]=dep[fa]+1,f[x][0]=fa;
	L[x]=++dfs_tot;
	v[dep[x]].push_back(L[x]);pos[dfs_tot]=x;
	for(int i=0;i<edge[x].size();i++){
		int to=edge[x][i];
		if(to==fa)continue;
		dfs(to,x);
	}
	R[x]=dfs_tot;
}
int up(int x,int k){
	for(int i=19;i>=0;i--)
		if(k&(1<<i))x=f[x][i];
	return x;
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++)A[i]=read();
    for(int i=1;i<n;i++){
    	int u=read(),v=read();
    	edge[u].push_back(v);
    	edge[v].push_back(u);
    }
	dfs(1,0);
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<v[i].size();j++){
			int to=v[i][j];
			++cnt;
			clo[to]=cnt;
			insert(tree[cnt-1],tree[cnt],1,n,A[pos[to]]);
		}
	}
	for(int i=1;i<20;i++)
    	for(int j=1;j<=n;j++)
    		f[j][i]=f[f[j][i-1]][i-1];
	int last=0,l,r;
    for(int i=1;i<=m;i++){
    	int a=read(),k=read(),x=(a^last)%n+1,fa=up(x,k),d=dep[x];
    	if(fa==0){puts("?");continue;}
		l=lower_bound(v[d].begin(),v[d].end(),L[fa])-v[d].begin(),
		r=upper_bound(v[d].begin(),v[d].end(),R[fa])-v[d].begin()-1;
		if(r-l+1<k){puts("?");continue;}
		int tl=v[d][l],tr=v[d][r];
		printf("%d\n",last=query(tree[clo[tl]-1],tree[clo[tr]],1,n,k));
    }
	return 0;
}

详情