相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4771
数据生成器:http://paste.ubuntu.com/24181811/
神犇题解:https://blog.sengxian.com/solutions/bzoj-4771
解题报告
这题sengxian又写了题解了,我又不想写了…..
不过,还是XJB说一说吧!题还是很好的
就是搞两类线段树,两类线段树都支持合并
其中一类线段树,下标是颜色的编号,叶子结点记录的是该种颜色的最浅深度,这个是用来更新第二类线段树的
另一类线段树的下标是深度,结点记录的是区间和,这个是用来回答询问的
我们先把第二类线段树给Merge起来,不过我们发现同一种颜色可能会算重
不过我们也可以发现,再Merge第一类线段树的时候,如果叶子结点重了
那么在第一类线段树里减掉深度较深的那个点之后,答案就没有问题了
另外的话,因为这题强制在线
于是我们还需要把第一类线段树给可持久化
总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = 1e7; int n,m,head[N],to[N],nxt[N],dep[N],col[N],fa[N]; inline int read() { char c=getchar(); int ret=0,f=1; 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; } class Segment_Tree_Sum{ int cnt,AnsTmp,root[N],ch[M][2],sum[M]; public: inline void modify(int w, int p, int delta) { modify(root[w], 1, n, p, delta); } inline void merge(int a, int b) { root[a] = Merge(root[a], root[b]); } inline int query(int w, int d) { AnsTmp = 0; query(root[w], 1, n, 1, d); return AnsTmp; } inline void init() { memset(root,0,sizeof(int)*(n+5)); memset(ch,0,sizeof(int)*(cnt+5)*2); memset(sum,0,sizeof(int)*(cnt+5)); cnt = 0; } private: void modify(int &w, int l, int r, int p, int delta) { w = cpy(w); sum[w] += delta; if (l < r) { int mid = l + r + 1 >> 1; if (p < mid) modify(ch[w][0], l, mid-1, p, delta); else modify(ch[w][1], mid, r, p, delta); } } int Merge(int a, int b) { a = a? cpy(a): 0; b = b? cpy(b): 0; if (!b || !a) return a + b; else { if (ch[a][0] || ch[a][1]) { ch[a][0] = Merge(ch[a][0], ch[b][0]); ch[a][1] = Merge(ch[a][1], ch[b][1]); } return sum[a] += sum[b], a; } } void query(int w, int l, int r, int L, int R) { if (L <= l && r <= R) AnsTmp += sum[w]; else { int mid = l + r + 1 >> 1; if (L < mid) query(ch[w][0], l, mid-1, L, R); if (mid <= R) query(ch[w][1], mid, r, L, R); } } inline int cpy(int b) { memcpy(ch[++cnt], ch[b], 8); sum[cnt] = sum[b]; return cnt; } }STS; class Segment_Tree_Col{ int cnt,root[N],ch[M][2],mn[M]; public: inline void insert(int w, int c) { insert(root[w], 1, n, c, dep[w]); STS.modify(w, dep[w], 1); } inline void merge(int a, int b) { STS.merge(a, b); root[a] = merge(root[a], root[b], a); } inline void init() { memset(root,0,sizeof(int)*(n+5)); memset(ch,0,sizeof(int)*(cnt+5)*2); memset(mn,0,sizeof(int)*(cnt+5)); cnt = 0; } private: void insert(int &w, int l, int r, int p, int v) { if (!w) w = ++cnt; if (l == r) mn[w] = v; else { int mid = l + r + 1 >> 1; if (p < mid) insert(ch[w][0], l, mid-1, p, v); else insert(ch[w][1], mid, r, p, v); } } int merge(int a, int b, int w) { if (!a || !b) return a + b; else if (ch[a][0] || ch[a][1]) { ch[a][0] = merge(ch[a][0], ch[b][0], w); ch[a][1] = merge(ch[a][1], ch[b][1], w); } else { STS.modify(w, max(mn[a], mn[b]), -1); mn[a] = min(mn[a], mn[b]); } return a; } }STC; int main() { for (int T=read();T;T--) { n = read(); m = read(); STS.init(); STC.init(); dep[1] = 1; for (int i=1;i<=n;i++) col[i] = read(); for (int i=2;i<=n;i++) dep[i] = dep[fa[i]=read()] + 1; for (int i=1;i<=n;i++) STC.insert(i, col[i]); for (int i=n;i>1;i--) STC.merge(fa[i], i); for (int i=1,x,d,last=0;i<=m;i++) { x = read() ^ last; d = read() ^ last; printf("%d\n",last=STS.query(x, dep[x]+d)); } } return 0; }
—————————— UPD 2017.4.11 ——————————
似乎Clairs之前出过这个题了…….
http://www.cnblogs.com/clrs97/p/5538804.html
What’s up everyone, it’s my first visit at this website, and piece of writing is really fruitful
in favor of me, keep up posting these articles
or reviews.
Hello, i read your blog from time to time and i own a similar one and i was just wondering if you get a lot of spam comments?
If so how do you protect against it, any plugin or anything
you can advise? I get so much lately it’s driving me mad so any support is very
much appreciated.
Way cool! Some very valid points! I appreciate
you writing this post and also the rest of the website is also really good.
Post writing is also a fun, if you be familiar with afterward you can write otherwise it is complex
to write.
Pretty great post. I just stumbled upon your blog and wanted to say that I have truly enjoyed
surfing around your blog posts. In any case
I’ll be subscribing for your feed and I am hoping you write once more soon!
Today, I went to the beachfront with my children. I found a
sea shell and gave it to my 4 year old daughter and said
“You can hear the ocean if you put this to your ear.” She placed the shell to her
ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is totally off topic but I
had to tell someone!
Hi there, just became aware of your blog through Google, and found
that it’s truly informative. I am going to watch out for brussels.
I’ll be grateful if you continue this in future. Numerous people
will be benefited from your writing. Cheers!
If you desire to get much from this piece of writing then you have
to apply such techniques to your won web site.
Awesome! Its in fact amazing piece of writing, I have
got much clear idea about from this paragraph.
Hi to all, the contents present at this site are actually
amazing for people knowledge, well, keep up the nice work fellows.
Hello, its nice article regarding media print, we all be aware of media is a great source of data.
Hello just wanted to give you a quick heads up. The text in your
article seem to be running off the screen in Opera. I’m not sure if
this is a formatting issue or something to do with internet browser compatibility but
I figured I’d post to let you know. The design and style
look great though! Hope you get the problem fixed soon. Kudos
Way cool! Some very valid points! I appreciate you writing this post
and also the rest of the site is extremely good.
Hi Dear, are you in fact visiting this web site regularly,
if so then you will absolutely get fastidious knowledge.
Hi, just wanted to mention, I loved this post.
It was helpful. Keep on posting!
Appreciate this post. Let me try it out.
After going over a handful of the blog posts on your web site,
I seriously appreciate your way of writing a blog.
I bookmarked it to my bookmark website list and will be checking back in the near future.
Take a look at my web site as well and let me know your opinion.
Hello! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing months of hard work due to no back up.
Do you have any solutions to stop hackers?
I know this web site provides quality dependent posts
and additional stuff, is there any other site which presents such things in quality?
Hello! This is my first comment here so I just wanted
to give a quick shout out and say I really enjoy reading your posts.
Can you recommend any other blogs/websites/forums that cover the same topics?
Appreciate it!
I always used to read post in news papers but now as I am a user of net so from now I am using
net for posts, thanks to web.
Genuinely when someone doesn’t understand then its up to other users
that they will help, so here it occurs.
You are so awesome! I don’t suppose I have read anything like
that before. So nice to find someone with some unique thoughts
on this subject. Seriously.. many thanks for starting this up.
This web site is something that is needed on the web, someone with a little originality!
Hey! Do you know if they make any plugins to help with
Search Engine Optimization? I’m trying to get my blog to rank
for some targeted keywords but I’m not seeing very good success.
If you know of any please share. Many thanks!
My brother recommended I might like this website.
He was totally right. This post truly made my day.
You can not imagine just how much time I had spent for this information!
Thanks! natalielise plenty of fish
Hello! I’m at work browsing your blog from my new apple
iphone! Just wanted to say I love reading through your blog and look forward to all your posts!
Keep up the excellent work!
Hey! I know this is kinda off topic but I was wondering if you knew where I could find a
captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having trouble finding one?
Thanks a lot!
It is not my first time to pay a quick visit this web site, i am visiting this website dailly
and take good data from here all the time.
What i don’t realize is if truth be told how you are now not actually a lot more smartly-preferred than you
may be now. You are very intelligent. You realize therefore considerably relating to this subject,
made me for my part consider it from numerous numerous angles.
Its like men and women aren’t interested unless it is something to accomplish with
Woman gaga! Your own stuffs outstanding. At all times maintain it up!
Fine way of telling, and pleasant paragraph
to take information regarding my presentation topic, which i am going to present in college.
Attractive section of content. I just stumbled
upon your weblog and in accession capital to assert that I acquire in fact enjoyed
account your blog posts. Anyway I’ll be subscribing to your augment and
even I achievement you access consistently quickly.
pof natalielise
Heya i am for the first time here. I found this board and I find It really useful & it helped me out a
lot. I hope to give something back and help others like you aided me.
Thank you for sharing your info. I really appreciate your efforts and I will be waiting
for your next write ups thank you once again.
Thank you for the good writeup. It in fact was
a amusement account it. Look advanced to far added agreeable from you!
However, how can we communicate?
Write more, thats all I have to say. Literally, it seems as though you relied on the
video to make your point. You obviously know what youre talking about, why
throw away your intelligence on just posting videos to your
blog when you could be giving us something enlightening to read?
Good day very nice web site!! Man .. Beautiful
.. Amazing .. I’ll bookmark your web site and take the feeds additionally?
I’m glad to seek out a lot of useful information here in the post, we need work out more techniques on this regard, thanks
for sharing. . . . . .
Greetings! Very useful advice in this particular article! It’s the little changes that produce the most significant changes.
Many thanks for sharing!
I could not refrain from commenting. Perfectly written!
Thanks for sharing such a good idea, article is nice, thats why i have read it entirely
Hey there, You’ve done a fantastic job. I will certainly digg it and
personally suggest to my friends. I’m sure they will be benefited
from this website.
Hmm is anyone else experiencing problems with the pictures on this blog loading?
I’m trying to determine if its a problem on my end or if it’s the
blog. Any suggestions would be greatly appreciated.
Hello there! I just would like to give you a huge thumbs up for the excellent info you have
got right here on this post. I will be returning to your site for more soon.
Hello mates, its impressive article concerning teachingand completely defined, keep it up all the time.
Hey there! This post could not be written any better!
Reading this post reminds me of my old room mate!
He always kept talking about this. I will forward this post to him.
Fairly certain he will have a good read. Many thanks for
sharing!
What i don’t realize is if truth be told how you are now
not really a lot more neatly-favored than you might be right
now. You’re so intelligent. You know thus considerably when it comes
to this matter, made me personally imagine it from numerous numerous angles.
Its like men and women are not fascinated until it is
one thing to accomplish with Lady gaga! Your own stuffs excellent.
All the time handle it up!
What’s Going down i am new to this, I stumbled upon this I’ve discovered It positively useful and it has
helped me out loads. I hope to contribute & assist different users like its helped me.
Good job.
I’m not sure where you’re getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for fantastic information I was looking for this info for my mission.
When someone writes an paragraph he/she retains the idea of a user in his/her mind that how
a user can understand it. Thus that’s why this article
is outstdanding. Thanks!
Sweet blog! I found it while surfing around on Yahoo
News. Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Appreciate it
I’m not that much of a online reader to be honest but your blogs really nice, keep it up!
I’ll go ahead and bookmark your site to come back in the future.
Many thanks
I think that what you said made a lot of sense.
However, what about this? what if you were to write a awesome headline?
I am not suggesting your information is not solid., but suppose you added something to maybe get a person’s
attention? I mean 【BZOJ 4771】七彩树 – Qizy's Database
is kinda plain. You could glance at Yahoo’s home page and note how they write news headlines to grab people to open the links.
You might add a related video or a related
picture or two to get people interested about what
you’ve got to say. Just my opinion, it might
make your posts a little livelier.
I’m really enjoying the design and layout of your
blog. It’s a very easy on the eyes which makes it much
more pleasant for me to come here and visit more
often. Did you hire out a designer to create your theme?
Superb work!
It’s actually a cool and useful piece of information. I’m satisfied that you simply
shared this helpful info with us. Please stay us up to date like this.
Thanks for sharing.
I do not know whether it’s just me or if perhaps everyone else experiencing problems with
your site. It appears like some of the text on your posts are running off the
screen. Can somebody else please provide feedback and
let me know if this is happening to them too?
This might be a problem with my web browser because I’ve had this happen before.
Thanks
I like the valuable information you provide in your articles.
I’ll bookmark your weblog and check again here frequently.
I’m quite certain I will learn many new stuff
right here! Best of luck for the next!
Your way of telling everything in this paragraph is truly
good, all be able to effortlessly be aware
of it, Thanks a lot.
Hi there would you mind stating which blog platform you’re using?
I’m going to start my own blog soon but I’m having a tough time deciding
between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most
blogs and I’m looking for something unique.
P.S My apologies for being off-topic but I had to ask!
With havin so much written content do you ever
run into any problems of plagorism or copyright infringement?
My site has a lot of unique content I’ve either authored myself
or outsourced but it looks like a lot of it is popping it up all over the internet
without my permission. Do you know any solutions to help reduce content from being
ripped off? I’d truly appreciate it.
Amazing! Its genuinely amazing post, I have got much clear idea on the topic of from this
piece of writing.
Very energetic article, I enjoyed that bit. Will there be a
part 2?
Thanks for sharing your thoughts about coconut oil where.
Regards
Ahaa, its good discussion concerning this paragraph here at this webpage, I have read all that, so at
this time me also commenting at this place.
I believe everything said made a bunch of sense.
But, think on this, what if you composed a catchier title?
I ain’t saying your content isn’t good., but what if you added a title that makes
people want more? I mean 【BZOJ 4771】七彩树 – Qizy's Database is kinda plain. You should glance
at Yahoo’s home page and watch how they write article headlines to grab people
interested. You might add a video or a related
pic or two to grab people interested about everything’ve written. Just my opinion, it would bring
your blog a little bit more interesting.
Fabulous, what a web site it is! This website gives
useful facts to us, keep it up.
I like the helpful information you provide on your articles.
I will bookmark your blog and test again right here
frequently. I’m rather sure I will learn plenty of new
stuff right here! Best of luck for the next!
Hi, I do believe this is an excellent site. I stumbledupon it 😉 I’m going to revisit yet again since
I bookmarked it. Money and freedom is the greatest way to change, may you be rich and continue to help others.
It’s the best time to make some plans for the future and it is time to be happy.
I have read this post and if I could I desire to suggest you few
interesting things or tips. Maybe you could write next
articles referring to this article. I wish to read even more things about it!
Wow, that’s what I was exploring for, what a information! present here at this
web site, thanks admin of this website.
I absolutely love your site.. Excellent colors & theme. Did you make this amazing site yourself?
Please reply back as I’m wanting to create my own site and would like to find out where
you got this from or exactly what the theme is named.
Thank you!
Currently it sounds like BlogEngine is the preferred blogging platform available right now.
(from what I’ve read) Is that what you’re using on your blog?
It’s truly very complex in this full of activity life to listen news on TV, so I only use
internet for that reason, and obtain the latest news.
Does your blog have a contact page? I’m having a tough time locating it
but, I’d like to send you an email. I’ve got some suggestions
for your blog you might be interested in hearing.
Either way, great blog and I look forward to seeing it develop over
time.
It’s an awesome piece of writing designed for all the online visitors; they will
obtain benefit from it I am sure.
Pretty! This was an extremely wonderful article. Thank you for supplying this information.
If you are going for best contents like I do, only pay a quick visit this website every day since it offers feature contents,
thanks
This paragraph is in fact a nice one it assists new net visitors,
who are wishing for blogging.
I’ve been browsing on-line greater than 3 hours
nowadays, yet I by no means discovered any fascinating
article like yours. It’s lovely price enough for me.
In my view, if all web owners and bloggers made just right content
as you probably did, the web will be much more useful than ever before.
Thanks for any other excellent post. The place else could anybody get that kind of information in such a perfect way of writing?
I have a presentation subsequent week, and I’m
on the look for such information.
You really make it seem so easy with your presentation but I find
this matter to be really something that I think I would never understand.
It seems too complicated and extremely broad for me. I am looking forward
for your next post, I will try to get the hang of it!
Good day! I know this is somewhat off topic but I was wondering which blog platform are you using for this site?
I’m getting tired of WordPress because I’ve
had issues with hackers and I’m looking at options for another
platform. I would be great if you could point me in the direction of a good platform.
When someone writes an post he/she retains the plan of a user in his/her brain that
how a user can know it. So that’s why this piece of writing is outstdanding.
Thanks!
Way cool! Some extremely valid points! I appreciate you
writing this article plus the rest of the website is very good.
Wonderful blog! I found it while surfing around on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Thanks
Pretty section of content. I just stumbled upon your web
site and in accession capital to assert that I get in fact enjoyed account your blog posts.
Anyway I will be subscribing to your augment and even I
achievement you access consistently rapidly.
Hello, i feel that i saw you visited my site so i got here to go back the want?.I am attempting to to find issues to enhance my website!I assume its
good enough to use a few of your concepts!!
Thank you for sharing with us, I believe this website really stands out : D.
We’re a gaggle of volunteers and starting a new scheme in our
community. Your web site offered us with useful info to work on. You’ve done a formidable activity
and our entire group will be thankful to you.
Hey just wanted to give you a quick heads up.
The words in your content seem to be running off the screen in Ie.
I’m not sure if this is a formatting issue or something to do with web browser compatibility but I
thought I’d post to let you know. The style and design look great though!
Hope you get the issue fixed soon. Cheers
When someone writes an post he/she maintains the plan of a user in his/her
mind that how a user can know it. So that’s why this paragraph is perfect.
Thanks!
Wow, superb blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your website is excellent,
let alone the content!
It’s difficult to find experienced people for this topic, however, you sound like you know what you’re
talking about! Thanks
Hurrah, that’s what I was seeking for, what a information! present here at this webpage, thanks admin of this website.
Hi, all the time i used to check web site posts here early in the dawn, as
i enjoy to learn more and more.
I am truly glad to glance at this website posts which contains lots of valuable information, thanks for providing such data.
Whats up very nice site!! Man .. Excellent .. Superb .. I’ll bookmark your site and take the feeds also?KI am glad to find numerous useful information right here in the put up, we’d like work out more techniques on this regard, thank you for sharing. . . . . .