Loading... ## 前言 这道题思维难度其实不难，难度在代码实现的方式。而我在这提供一个需要费点脑子但是好写一些的实现方式。这样做可以节约很多比赛时间，毕竟比赛做题用时越少越好。 ## 正文 ### 0x01 问题分析 根据题面，得出需要在一个树上维护两个操作： 1. 标记某个点。 2. 查询在某个时刻，某两个点之间第 $k$ 个没有被标记的店。 显然可以用树链剖分+主席树解决，主席树维护某个区间在某个时间点被标记的数量。然后由于一个点不会被标记两次，故使用前缀和思想，**这段时间内被标记的数量=当前被标记的数量- $y$ 这个时刻被标记的数量**。 那么二分去找第 $k$ 个没有被标记的点即可。但是直接二分时间复杂度会达到 $\mathcal{O}\left(n\log ^3 n\right)$ ，但是可以考虑 **先从当前节点走一些重链，最后在一个重链里面二分** $\mathcal{O}\left(n\log ^2 n\right)$ 。 ### 0x02 代码实现 首先处理 $k$ 不包含 $a$ 和 $b$ 两个端点的问题，这里可以对 $k$ 加上 $1$ 如果 $a$ 没有被标记的话，被标记则不管。这样处理可以直接在 $a$ $b$ 两个点之间二分。 其次我们并不需要像其他题解一样记录下路径上的重链剖分结果，可以考虑先找出他们的lca，计算 $a$ 到 $b$ 、 $a$ 到 $lca$ 上没有被标记的数量，然后进行判断在那一段上还是无解。若在 $a$ 到 $lca$ 这段上，直接网上二分到第 $k$ 个没有被标记的点；若在 $b$ 到 $lca$ 这段上，可以倒着二分，但是也可以先计算出第 $k$ 没被标记的点，在 $b$ 上面几个点，记为 $k_2$ 然后同样从 $a$ 向上二分即可。 ```cpp #include<cstdio> #include<vector> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;} int arr[100010]; #define PSEG_TREE_DATA_TYPE int const int PSEG_DATA_SIZE=100010; const int PSEG_SIZE=PSEG_DATA_SIZE*20; struct PSEG_TREE_NODE{ PSEG_TREE_DATA_TYPE data; int lChild,rChild; }; //主席树模板 struct PSEG_TREE{ PSEG_TREE_NODE tree[PSEG_SIZE]; int root[PSEG_SIZE],tot; int getNewMem(){ return tot++; } int build(int l,int r){ int p=getNewMem(); if(l==r) tree[p].data=0; else{ int mid=(l+r)>>1; tree[p].lChild=build(l,mid); tree[p].rChild=build(mid+1,r); push_up(p); } return p; } int update(int pos,int s,int t,int old){ int p=getNewMem(); tree[p]=tree[old]; if(s==t) tree[p].data=1; else{ int mid=s+((t-s)>>1); if(pos<=mid) tree[p].lChild=update(pos,s,mid,tree[p].lChild); else tree[p].rChild=update(pos,mid+1,t,tree[p].rChild); push_up(p); } return p; } PSEG_TREE_DATA_TYPE query(int l,int r,int s,int t,int p){ if(l<=s&&t<=r) return tree[p].data; int mid=s+((t-s)>>1); return ((l<=mid)?query(l,r,s,mid,tree[p].lChild):0)+((r>mid)?query(l,r,mid+1,t,tree[p].rChild):0); } void push_up(int p){ tree[p].data=tree[tree[p].lChild].data+tree[tree[p].rChild].data; return; } }pseg; std::vector<int> e[100010]; int n,cntid,depths[100010],cnttree[100010],id[100010],sid[100010],parents[100010],linktop[100010],hson[100010]; void addEdge(int u,int v){ e[u].push_back(v); } int uPseg(int pos,int version){ return pseg.update(pos,1,n,pseg.root[version]); } int qPseg(int l,int r,int version,int now){ return r-l+1-pseg.query(l,r,1,n,pseg.root[now])+pseg.query(l,r,1,n,pseg.root[version]); } void dfsinit(int u,int p){ parents[u]=p; depths[u]=depths[p]+1; cnttree[u]=1; for(auto v:e[u]) if(v!=p){ dfsinit(v,u); cnttree[u]+=cnttree[v]; if(cnttree[hson[u]]<cnttree[v]) hson[u]=v; } } void dfslink(int u,int top){ id[u]=++cntid; sid[id[u]]=u; linktop[u]=top; if(!hson[u]) return; dfslink(hson[u],top); for(auto v:e[u]) if(v!=parents[u]&&v!=hson[u]) dfslink(v,v); } int getLca(register int u,register int v){ while(linktop[u]!=linktop[v]){ if(depths[linktop[u]]<depths[linktop[v]]) u^=v^=u^=v; u=parents[linktop[u]]; } if(depths[u]>depths[v]) u^=v^=u^=v; return u; } int rangeQuery(int u,int v,int version,int now){ register int res=0; while(linktop[u]!=linktop[v]){ if(depths[linktop[u]]<depths[linktop[v]]) u^=v^=u^=v; res+=qPseg(id[linktop[u]],id[u],version,now); u=parents[linktop[u]]; } if(depths[u]>depths[v]) u^=v^=u^=v; res+=qPseg(id[u],id[v],version,now); return res; } int search(int u,int val,int version,int now){ //先向上走重链 while(qPseg(id[linktop[u]],id[u],version,now)<val&&u) val-=qPseg(id[linktop[u]],id[u],version,now),u=parents[linktop[u]]; register int l,r,mid; l=id[linktop[u]],r=id[u]; //二分剩下一截 val=qPseg(id[linktop[u]],id[u],version,now)-val+1; while(l<r){ mid=(l+r)>>1; if(qPseg(id[linktop[u]],mid,version,now)<val) l=mid+1; else r=mid; } return sid[l]; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register char op; register int i,val,root,u,v,version,lca,all,left; n=read(); for(u=1;u<=n;++u){ v=read(); if(v){ addEdge(u,v); addEdge(v,u); }else root=u; } dfsinit(root,0); dfslink(root,root); pseg.root[0]=pseg.build(1,n); int q=read(); for(i=1;i<=q;++i){ op=read(); if(op==1) pseg.root[i]=uPseg(id[read()],i-1); else{ pseg.root[i]=pseg.root[i-1]; u=read(); v=read(); val=read(); version=read(); //技巧性处理 val+=qPseg(id[u],id[u],version,i); lca=getLca(u,v); all=rangeQuery(u,v,version,i); left=rangeQuery(u,lca,version,i); //注意无解判断方式 if((all<=val&&qPseg(id[v],id[v],version,i))||(all<val)) puts("-1"); else{ if(val<=left)//a到lca一段 print(search(u,val,version,i)); else{//b到lca一段 val=all-val+1; print(search(v,val,version,i)); } putchar('\n'); } } } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2023 年 11 月 10 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏