| 记录编号 |
385148 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015]奈特 |
最终得分 |
100 |
| 用户昵称 |
 liu_runda |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.057 s |
| 提交时间 |
2017-03-20 12:25:11 |
内存使用 |
70.10 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct edge{
int to,next;
}lst[maxn<<1];int first[maxn],len=1;
void addedge(int a,int b){
lst[len].to=b;lst[len].next=first[a];first[a]=len++;
}
int n,root;
int prt[maxn],sz[maxn],top[maxn],depth[maxn],hvy[maxn],dfn[maxn],T;
void dfs1(int x){
sz[x]=1;
for(int pt=first[x];pt;pt=lst[pt].next){
depth[lst[pt].to]=depth[x]+1;
dfs1(lst[pt].to);
sz[x]+=sz[lst[pt].to];
if(sz[lst[pt].to]>sz[hvy[x]])hvy[x]=lst[pt].to;
}
}
void dfs2(int x){
dfn[x]=++T;
if(hvy[x]){
top[hvy[x]]=top[x];dfs2(hvy[x]);
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==hvy[x])continue;
top[lst[pt].to]=lst[pt].to;
dfs2(lst[pt].to);
}
}
}
struct node{
node* ch[2];int sum;
node(){}
node(int x){sum=x;ch[0]=ch[1]=0;}
}t[maxn*50];int trsz=0;
node* newnode(int x){
t[++trsz]=node(x);return t+trsz;
}
node* Root[maxn];
void Insert(node* rt0,node* &rt,int l,int r,int k){
rt=newnode(rt0->sum+1);
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid){
Insert(rt0->ch[0],rt->ch[0],l,mid,k);
rt->ch[1]=rt0->ch[1];
}else{
Insert(rt0->ch[1],rt->ch[1],mid+1,r,k);
rt->ch[0]=rt0->ch[0];
}
}
int qsum(node* rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return rt->sum;
int mid=(l+r)>>1,ans=0;
if(ql<=mid)ans+=qsum(rt->ch[0],l,mid,ql,qr);
if(qr>mid) ans+=qsum(rt->ch[1],mid+1,r,ql,qr);
return ans;
}
int seg[maxn<<2];
void Insert(int rt,int l,int r,int k){
seg[rt]++;
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid)Insert(rt<<1,l,mid,k);
else Insert(rt<<1|1,mid+1,r,k);
}
int qsum(int rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return seg[rt];
}
int ans=0,mid=(l+r)>>1;
if(ql<=mid)ans+=qsum(rt<<1,l,mid,ql,qr);
if(qr>mid) ans+=qsum(rt<<1|1,mid+1,r,ql,qr);
return ans;
}
int ans[maxn];
struct event{
int typ,u,v,k,val,num,T;
bool operator <(const event &B)const{
return (val==B.val)?typ<B.typ:val<B.val;
}
}E[maxn*2];
int hit[maxn];
int LCA,sum1=0,sum2=0;
int pathsum(int u,int v,int T){
int t1=top[u],t2=top[v];
sum1=sum2=0;
while(t1!=t2){
if(depth[t1]<depth[t2]){
sum2+=qsum(1,1,n,dfn[t2],dfn[v]);sum2+=qsum(Root[T],1,n,dfn[t2],dfn[v]);
v=prt[t2];t2=top[v];
}else{
sum1+=qsum(1,1,n,dfn[t1],dfn[u]);sum1+=qsum(Root[T],1,n,dfn[t1],dfn[u]);
u=prt[t1];t1=top[u];
}
}
if(depth[u]>depth[v]){
LCA=v;sum1+=qsum(1,1,n,dfn[v],dfn[u]);sum1+=qsum(Root[T],1,n,dfn[v],dfn[u]);
}else{
LCA=u;sum2+=qsum(1,1,n,dfn[u],dfn[v]);sum2+=qsum(Root[T],1,n,dfn[u],dfn[v]);
}
return sum1+sum2;
}
int qkth(int rt,node* rt2,int l,int r,int ql,int qr,int k){//from right to left
if(l==r)return l;
int mid=(l+r)>>1;
if(qr<=mid)return qkth(rt<<1,rt2->ch[0],l,mid,ql,qr,k);
int tmp=qsum(rt<<1|1,mid+1,r,ql,qr)+qsum(rt2->ch[1],mid+1,r,ql,qr);
if(k<=tmp)return qkth(rt<<1|1,rt2->ch[1],mid+1,r,ql,qr,k);
else return qkth(rt<<1,rt2->ch[0],l,mid,ql,qr,k-tmp);
}
int kth(int lim,int u,int k,int T){
int t=top[u];
while(1){
int tmp=qsum(1,1,n,dfn[t],dfn[u])+qsum(Root[T],1,n,dfn[t],dfn[u]);
if(tmp>=k)return qkth(1,Root[T],1,n,dfn[t],dfn[u],k);
else{
k-=tmp;u=prt[t];t=top[u];
}
}
}
int query(int u,int v,int k,int T){
int wu=qsum(1,1,n,dfn[u],dfn[u])+qsum(Root[T],1,n,dfn[u],dfn[u]);
int wv=qsum(1,1,n,dfn[v],dfn[v])+qsum(Root[T],1,n,dfn[v],dfn[v]);
int ww=pathsum(u,v,T);
if(ww-wu-wv<k)return -1;
else{
if(sum1-wu>=k)return kth(LCA,prt[u],k,T);
else return kth(LCA,prt[v],(ww-wu-wv-k+1),T);
}
}
int point[maxn];
int main(){
freopen("K_night.in","r",stdin);
freopen("K_night.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&prt[i]);
for(int i=1;i<=n;++i){
if(prt[i])addedge(prt[i],i);
else root=i;
}
depth[root]=1;dfs1(root);top[root]=root;dfs2(root);
int m;scanf("%d",&m);
int cntq=0;
Root[m+1]=t+0;Root[m+1]->ch[0]=Root[m+1]->ch[1]=t+0;
Root[m+1]->sum=0;
for(int i=1;i<=m;++i){
scanf("%d",&E[i].typ);
if(E[i].typ==1){
scanf("%d",&E[i].u);E[i].val=i;hit[E[i].u]=i;
}
else{
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].k,&E[i].val);E[i].num=++cntq;E[i].T=i;
}
}
for(int i=m;i>=1;--i){
Root[i]=Root[i+1];
if(E[i].typ==1){
Insert(Root[i],Root[i],1,n,dfn[E[i].u]);
}
}
for(int i=1;i<=n;++i){
if(!hit[i])Insert(1,1,n,dfn[i]);
}
sort(E+1,E+m+1);
for(int i=1;i<=m;++i){
if(E[i].typ==1)Insert(1,1,n,dfn[E[i].u]);
else{
ans[E[i].num]=query(E[i].u,E[i].v,E[i].k,E[i].T);
}
}
for(int i=1;i<=n;++i)point[dfn[i]]=i;
for(int i=1;i<=cntq;++i){
if(ans[i]!=-1)printf("%d\n",point[ans[i]]);
else printf("-1\n");
}
return 0;
}