首页 > 代码库 > CodeForces 797D Broken BST
CodeForces 797D Broken BST
$dfs$,线段树。
通过观察可以发现,某位置要能被找到,和他到根这条路上的每个节点的权值存在密切的联系,且是父节点的做儿子还是有儿子也有联系。
可以从根开始$dfs$,边走边更新线段树,如果遍历左儿子,那么将$[1,val-1]$全部加$1$,否则将$[val+1,n]$全部加$1$,回溯的时候减$1$,判断某位置能否到达可以比较单点值与深度的关系。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <queue>#include <stack>#include <vector>#include <algorithm>using namespace std;int f[400010];int s[400010];int res;void pushDown(int rt){ if(f[rt]==0) return ; s[2*rt] += f[rt]; s[2*rt+1] += f[rt]; f[2*rt] += f[rt]; f[2*rt+1] += f[rt]; f[rt] = 0; return ;}void pushUp(int rt){ s[rt] = s[2*rt] + s[2*rt+1];}void update(int L,int R,int val,int l,int r,int rt){ if(L<=l&&r<=R) { s[rt] += val; f[rt] += val; return ; } int m = (l+r)/2; pushDown(rt); if(L<=m) update(L,R,val,l,m,2*rt); if(R>m) update(L,R,val,m+1,r,2*rt+1); pushUp(rt);}void query(int pos,int l,int r,int rt){ if(l==r) { res = s[rt]; return; } int m = (l+r)/2; pushDown(rt); if(pos<=m) query(pos,l,m,2*rt); else query(pos,m+1,r,2*rt+1); pushUp(rt);}int n;struct X{ int val; int left,right;}node[100010];int root;int b[100010],sz;int ans;int get(int x){ int L = 0,R = sz-1; while(L<=R) { int mid = (L+R)/2; if(b[mid]>x) R = mid-1; else if(b[mid] == x) return mid+1; else L = mid+1; }}int u[100010];void dfs(int x,int y){ query(node[x].val,1,n,1); if(res != y) {} else u[node[x].val]=1; if(node[x].left!=-1) { if(node[x].val>1) update(1,node[x].val-1,1,1,n,1); dfs(node[x].left,y+1); if(node[x].val>1) update(1,node[x].val-1,-1,1,n,1); } if(node[x].right!=-1) { if(node[x].val<n) update(node[x].val+1,n,1,1,n,1); dfs(node[x].right,y+1); if(node[x].val<n) update(node[x].val+1,n,-1,1,n,1); } }int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&node[i].val,&node[i].left,&node[i].right); for(int i=1;i<=n;i++) b[sz++] = node[i].val; sort(b,b+sz); for(int i=1;i<=n;i++) { node[i].val = get(node[i].val); u[node[i].val]=1; } int sum=0; for(int i=1;i<=n;i++) sum=sum+1; for(int i=1;i<=n;i++) { if(node[i].left!=-1) f[node[i].left] = 1; if(node[i].right!=-1) f[node[i].right] = 1; } for(int i=1;i<=n;i++) { if(f[i]) continue; root = i; break; } memset(f,0,sizeof f); memset(u,0,sizeof u); dfs(root,0); for(int i=1;i<=n;i++) sum=sum-u[node[i].val]; printf("%d\n",sum); return 0;}
CodeForces 797D Broken BST
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。