【BZOJ 4771】七彩树

相关链接

题目传送门: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

95 thoughts to “【BZOJ 4771】七彩树”

  1. 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.

  2. 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.

  3. 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!

  4. 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!

  5. 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!

  6. 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

  7. 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.

  8. 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!

  9. 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!

  10. 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!

  11. 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

  12. 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!

  13. 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!

  14. 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

  15. 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?

  16. 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. . . . . .

  17. 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.

  18. 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.

  19. 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!

  20. 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!

  21. 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.

  22. 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.

  23. 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!

  24. 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

  25. 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.

  26. 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!

  27. 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.

  28. 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

  29. 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!

  30. 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!

  31. 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.

  32. 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.

  33. 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!

  34. 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!

  35. 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.

  36. 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.

  37. 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.

  38. 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!

  39. 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.

  40. 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!

  41. 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

  42. 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.

  43. 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!!

  44. 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.

  45. 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

  46. 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!

  47. 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. . . . . .

Leave a Reply to how to get help in windows 10 Cancel reply

Your email address will not be published. Required fields are marked *