[x]=size[last]+del; lc[x]=rc[x]=0; if (l==r) return x; if (k<=mid) lc[x]=update(l,mid,lc[last],k,del),rc[x]=rc[last];else rc[x]=update(mid+1,r,rc[last],k,del),lc[x]=lc[last]; return x; } void dfs(int x) { fa[x]=x;L[x]=++tim;u[x]=0; root[x]=update(1,tot,root[pre[x]],q[x],1); for (int j=a[x];j;j=ed[j].next) if (ed[j].e!=pre[x]) { d[ed[j].e]=d[x]+1;pre[ed[j].e]=x; dfs(ed[j].e);fa[ed[j].e]=x; } R[x]=tim;u[x]=1; for (int j=h[x];j;j=ed[j].next) if (u[ed[j].e]) lca[ed[j].xu]=getfa(ed[j].e); } void change(int x,int k,int del) { for (int i=x;i<=n;i+=lowbit(i)) c[i]=update(1,tot,c[i],k,del); } void get(int x,int kind) { for (int i=x;i;i-=lowbit(i)) use[++sum[kind]][kind]=c[i]; } int calc(int kind) { int ans=0; for (int i=1;i<=sum[kind];i++) ans+=size[rc[use[i][kind]]]; return ans; } void next(int kind,int dir) { for (int i=1;i<=sum[kind];i++) use[i][kind]=dir?rc[use[i][kind]]:lc[use[i][kind]]; } void query(int p,int x,int y,int k) { if (d[x]+d[y]-2*d[p]+1
>1; now=size[rc[ux]]+calc(1)+size[rc[uy]]-2*(calc(0)+size[rc[up]]); if (f)now+=(q[p]>mid); if (now>=k) { next(1,1);next(0,1);ux=rc[ux];uy=rc[uy];up=rc[up]; l=mid+1; } else { next(1,0);next(0,0);ux=lc[ux];uy=lc[uy];up=lc[up]; if (q[p]>mid) f=false; r=mid,k-=now; } } printf("%d\n",newq[l]); } int main() { scanf("%d%d",&n,&Q); for (i=1;i<=n;i++) { scanf("%d",&q[i]); num[++cnt]=node(q[i],i); a[i]=h[i]=c[i]=0; } for (i=1;i
n) y[num[i].yuan-n]=tot;else q[num[i].yuan]=tot; } d[(n+1)/2]=0;pre[(n+1)/2]=0;root[0]=0;lc[0]=rc[0]=0;size[0]=0; dfs((n+1)/2); for (i=1;i<=Q;i++) if (k[i]) query(lca[i],x[i],y[i],k[i]); else { change(L[x[i]],q[x[i]],-1);change(R[x[i]]+1,q[x[i]],1); change(L[x[i]],y[i],1);change(R[x[i]]+1,y[i],-1); q[x[i]]=y[i]; } }
?
|