相关链接
题目传送门：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;
}
Woah! I’m really enjoying the template/theme of this
site. It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between superb usability and appearance.
I must say that you’ve done a great job
with this. In addition, the blog loads super fast for me on Opera.
Superb Blog!
We are a group of volunteers and opening a new scheme in our community.
Your site offered us with valuable information to work on.
You have done a formidable job and our whole community will be
grateful to you.
Everything is very open with a very clear description of the challenges.
It was really informative. Your website is very helpful. Thanks for sharing!
I’ve been surfing on-line more than three hours today, yet I never found
any interesting article like yours. It is beautiful
price sufficient for me. In my opinion, if all webmasters
and bloggers made just right content material as you did, the internet might be much more useful than ever before.
Heya i’m for the primary time here. I found this board and I to find It truly helpful & it helped me out much.
I am hoping to present something back and aid others such as you helped me.
I think this is among the most important info for me.
And i am glad reading your article. But wanna
remark on few general things, The web site style is perfect, the articles is really excellent : D.
Good job, cheers
I am really loving the theme/design of your blog. Do you ever
run into any browser compatibility issues? A handful
of my blog visitors have complained about my
blog not operating correctly in Explorer but looks great in Opera.
Do you have any tips to help fix this issue?
Hmm it appears like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I as well am an aspiring blog blogger but I’m still new to
the whole thing. Do you have any helpful hints for novice blog writers?
I’d definitely appreciate it.
Hello, i believe that i saw you visited my site
thus i got here to go back the desire?.I’m attempting to find things
to improve my web site!I assume its ok to make use of
a few of your ideas!!
I’m not that much of a internet reader to be honest but your blogs
really nice, keep it up! I’ll go ahead and bookmark your website to come back later.
Cheers
Hello there, just became aware of your blog through Google, and found that it is truly
informative. I am going to watch out for brussels. I’ll be grateful
if you continue this in future. A lot of people will be benefited from your writing.
Cheers!
Oh my goodness! an incredible article dude. Thank you However I’m experiencing issue with ur rss . Don’t know why Unable to subscribe to it. Is there anyone getting identical rss downside? Anyone who is aware of kindly respond. Thnkx
Amazing issues here. I’m very happy to look your article.
Thanks so much and I’m having a look forward to touch
you. Will you kindly drop me a mail?
What i do not realize is in reality how you’re now not actually much more smartly-preferred than you may be now.
You are so intelligent. You understand therefore significantly when it comes to this subject,
produced me in my opinion imagine it from so many numerous angles.
Its like men and women don’t seem to be involved unless it is one thing to
accomplish with Lady gaga! Your own stuffs nice.
At all times handle it up!
Greetings! I know this is kinda off topic but I was wondering which blog platform are you
using for this website? I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at alternatives for
another platform. I would be awesome if you could point me in the direction of a good platform.
What i do not understood is if truth be told how you’re no longer really much more smartly-liked than you may be right now.
You’re so intelligent. You know thus considerably on the subject of this matter, made me
for my part consider it from so many various angles. Its like women and men are not involved unless it’s one
thing to accomplish with Lady gaga! Your own stuffs excellent.
At all times care for it up!
Hi to every one, it’s in fact a good for me to pay a
visit this website, it contains valuable Information.
This design is incredible! You obviously know how to
keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really enjoyed what you had to say, and more
than that, how you presented it. Too cool!
I have been exploring for a little for any high-quality articles or blog posts in this kind of house .
Exploring in Yahoo I finally stumbled upon this site.
Studying this info So i’m glad to convey that I have an incredibly excellent uncanny feeling
I discovered exactly what I needed. I most unquestionably will make sure to don?t disregard this web site and provides it a glance on a constant basis.
My developer is trying to persuade me to
move to .net from PHP. I have always disliked the idea because of the
expenses. But he’s tryiong none the less. I’ve been using WordPress on a number of websites for about a year and am concerned about switching to another platform.
I have heard good things about blogengine.net.
Is there a way I can import all my wordpress content into it?
Any help would be really appreciated!
This piece of writing is actually a good one it assists new web visitors, who
are wishing for blogging.
As a Newbie, I am continuously exploring online for articles that can help me. Thank you