相关链接
题目传送门:http://codeforces.com/contest/797/problem/D
解题报告
之前做过类似的题:http://oi.cyo.ng/?p=298
大概就是说,排序之后,每个点的左右子树切换至多发生一次
于是用基排来离散化的话,时间复杂度就是:$O(n)$的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; int n,rt,is_rt[N],val[N],ch[N][2],TOT[N]; int tot,_hash[N],cnt[N],dep[N],vout; set<pair<int,int> > id[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } void dfs(int w, int f) { dep[w] = dep[f] + 1; if (ch[w][1]) dfs(ch[w][1], w); if (ch[w][0]) dfs(ch[w][0], w); } void add(int w, int sta) { if (w <= 0) return; id[val[w]].insert(make_pair(dep[w], w)); cnt[val[w]]++; if (val[w] > sta) add(ch[w][0], sta); else add(ch[w][1], sta); } void del(int w, int sta) { if (w <= 0) return; id[val[w]].erase(make_pair(dep[w], w)); cnt[val[w]]--; if (val[w] > sta) del(ch[w][0], sta); else del(ch[w][1], sta); } int main() { n = read(); for (int i=1,l,r;i<=n;i++) { val[i] = read(); _hash[++tot] = val[i]; if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1; if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1; } for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;} dfs(rt, rt); sort(_hash+1, _hash+1+tot); tot = unique(_hash+1, _hash+1+tot) - _hash - 1; for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++; add(rt, 1); if (!cnt[1]) vout += TOT[1]; for (int i=2,w;i<=tot;i++) { if (id[i].size() > 0) { auto tmp = id[i].begin(); w = tmp->second; del(w, i-1); add(w, i); } if (cnt[i] == 0) vout += TOT[i]; } printf("%d\n",vout); return 0; }