【BZOJ 4571】[SCOI2016] 美味

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4571

考试的时候,找了一个小时的规律,总觉得加法在二进制下有奇特的规律
考完试后知道真相的我,哭晕在厕所…

仍然考虑按位贪心
于是发现高位确定,低位不确定在十进制下是一个区间,于是搞一搞函数式线段树
仔细想一想,一般的Xor问题也可以这么做,trie树只是一个特殊的优化

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N * 18;

int arr[N],n,m,MX; 

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;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N];
	int ans_tmp,L,R;
	
	void build(int p, int &w, int l, int r, int cur) {
		w = ++cnt; memcpy(ch[w],ch[p],sizeof(ch[w]));
		sum[w] = sum[p] + 1; if (l < r) {
			int mid = l + r + 1 >> 1;
			if (cur < mid) build(ch[p][0],ch[w][0],l,mid-1,cur);
			else build(ch[p][1],ch[w][1],mid,r,cur);
		}
	}
	
	inline void Build_Tree() {
		for (int i=1;i<=n;i++) 
			build(root[i-1],root[i],0,MX,arr[i]);
	}
	
	void ask(int w, int l, int r, int f) {
		if (L <= l && r <= R) ans_tmp += sum[w]*f;
		else if (w) {
			int mid = l + r + 1 >> 1;
			if (L < mid) ask(ch[w][0],l,mid-1,f);
			if (R >= mid) ask(ch[w][1],mid,r,f);
		}
	}
	
	inline int Query(int r1, int r2, int l, int r) {
		l = max(0,l); r = min(MX,r); 
		if (l > r) return 0;
		
		ans_tmp = 0; L = l; R = r;
		ask(r1,0,MX,-1); ask(r2,0,MX,1);
		return ans_tmp;
	}
	
	inline int query(int b, int x, int l, int r){
		int ret = 0, r1 = root[l-1], r2 = root[r];
		for (int i=17;~i;i--) {
			int c = (b & (1<<i)) ^ (1<<i); 
			if (Query(r1,r2,ret+c-x,ret+c+(1<<i)-1-x)) ret += c;
			else ret += c ^ (1<<i);
		} return ret^b;
	}
};

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) MX = max(MX, arr[i]=read());
	CT::Build_Tree();
	for (int i=1,b,x,l,r;i<=m;i++) {
		b = read(); x = read(); 
		l = read(); r = read();
		printf("%d\n",CT::query(b,x,l,r));
	}
	return 0;
}

279 thoughts to “【BZOJ 4571】[SCOI2016] 美味”

  1. Oh my goodness! Amazing article dude! Thank you so much, However I am going through problems with your RSS.
    I don’t know why I am unable to join it. Is there anybody
    else having similar RSS issues? Anybody who knows the answer can you kindly respond?
    Thanks!!

  2. Thanks for one’s marvelous posting! I truly enjoyed reading it, you might be
    a great author. I will be sure to bookmark your blog and
    may come back later in life. I want to encourage you continue your great posts, have a nice evening!

  3. Its like you read my mind! You appear to know so much about this, like you
    wrote the book in it or something. I think that you could do with some pics to drive the message home a little
    bit, but instead of that, this is great blog.
    An excellent read. I will definitely be back.

  4. Hi there, I found your web site by the use of Google whilst looking for a similar subject, your website came
    up, it seems good. I’ve bookmarked it in my google bookmarks.

    Hi there, just became aware of your blog through Google, and located that it is really informative.

    I am gonna watch out for brussels. I will be grateful when you continue
    this in future. Lots of folks will be benefited out of your
    writing. Cheers!

  5. A motivating discussion is worth comment.

    I think that you need to publish more on this subject matter, it might not be a taboo matter but generally folks don’t speak about these issues.
    To the next! Many thanks!!

  6. We are a gaggle of volunteers and starting a new
    scheme in our community. Your website offered us with useful information to work on. You have done an impressive activity and our entire
    community shall be thankful to you.

  7. It is appropriate time to make some plans for the future and it’s time to be happy.
    I have learn this publish and if I could I desire to recommend you some fascinating
    things or tips. Maybe you could write subsequent articles referring to
    this article. I want to read even more issues approximately
    it!

  8. I believe that is among the most important information for
    me. And i am glad reading your article. However should remark
    on some general issues, The web site taste is ideal, the
    articles is in reality great : D. Good activity,
    cheers

  9. Hello! I could have sworn I’ve been to this site before but
    after checking through some of the post I realized
    it’s new to me. Nonetheless, I’m definitely delighted I found it and I’ll be bookmarking
    and checking back frequently!

  10. Hello everybody, here every one is sharing these kinds of knowledge, thus it’s fastidious to read this webpage, and I used to
    visit this weblog daily. natalielise plenty of fish

  11. It’s the best time to make some plans for the future and it’s time to
    be happy. I’ve read this post and if I could I desire to
    suggest you some interesting things or advice. Perhaps you
    could write next articles referring to this
    article. I wish to read more things about it!

  12. First off I want to say awesome blog! I had a quick question that I’d like to
    ask if you don’t mind. I was interested to find out how you center yourself and clear your mind before writing.

    I’ve had a tough time clearing my thoughts in getting my ideas out there.
    I truly do take pleasure in writing however it just seems like the first 10
    to 15 minutes are usually lost just trying to figure
    out how to begin. Any ideas or tips? Cheers!

  13. excellent issues altogether, you simply gained
    a brand new reader. What might you recommend about your put up that you just
    made a few days in the past? Any positive?

  14. Have you ever considered about adding a little bit more than just your articles?
    I mean, what you say is fundamental and all. However just imagine
    if you added some great pictures or video clips to give your posts more, “pop”!
    Your content is excellent but with images and clips, this blog could definitely be one of the best in its field.
    Very good blog! natalielise plenty of fish

  15. We are a group of volunteers and opening a new scheme in our
    community. Your website provided us with valuable info to
    work on. You’ve done an impressive job and our whole
    community will be thankful to you.

  16. Thanks for another wonderful article. The place else may
    just anybody get that type of info in such an ideal means of writing?
    I’ve a presentation subsequent week, and I’m on the look for such info.

  17. I was suggested this blog by my cousin. I’m not sure whether this post
    is written by him as no one else know such detailed about my problem.
    You’re incredible! Thanks!

  18. I’m curious to find out what blog platform you’re using?
    I’m having some small security issues with my latest blog and
    I would like to find something more risk-free. Do you have any suggestions?

  19. I’m amazed, I have to admit. Rarely do I encounter a blog
    that’s both educative and engaging, and without a doubt,
    you’ve hit the nail on the head. The problem is something which too few men and women are speaking
    intelligently about. Now i’m very happy I came across this in my search for something relating to this.

  20. Excellent post. Keep posting such kind of info on your blog.
    Im really impressed by it.
    Hello there, You have done a fantastic job. I’ll certainly digg it and personally
    recommend to my friends. I am confident they’ll be benefited from this
    site.

  21. I will immediately take hold of your rss feed as I can not find
    your email subscription hyperlink or newsletter service.
    Do you’ve any? Kindly permit me recognize in order that I could subscribe.

    Thanks.

  22. Today, I went to the beach front 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!

  23. Hello there! This blog post could not be written any better!
    Reading through this post reminds me of my previous roommate!
    He constantly kept talking about this. I will forward this information to
    him. Fairly certain he will have a very good read.
    Thank you for sharing!

  24. Howdy! I could have sworn I’ve been to this site before but
    after browsing through some of the post I realized it’s new to me.
    Nonetheless, I’m definitely glad I found it and I’ll
    be book-marking and checking back frequently!

  25. Undeniably consider that which you stated. Your favourite reason appeared
    to be at the net the simplest thing to take into account of.
    I say to you, I definitely get irked at the
    same time as people consider concerns that they plainly don’t recognise
    about. You controlled to hit the nail upon the top and outlined out the entire
    thing without having side-effects , other folks could take a signal.
    Will probably be again to get more. Thank you

  26. I am really impressed with your writing skills and also with the layout on your weblog.
    Is this a paid theme or did you modify it your self? Either way stay
    up the nice high quality writing, it is uncommon to see a great
    weblog like this one these days..

  27. I like the valuable information you provide in your articles.

    I will bookmark your blog and check again here
    regularly. I’m quite certain I will learn plenty
    of new stuff right here! Best of luck for the next!

  28. I do not even know how I stopped up here, however I believed
    this publish was once great. I do not understand who you are but certainly
    you’re going to a well-known blogger in the event you aren’t already.
    Cheers!

  29. Excellent beat ! I would like to apprentice even as you amend your
    site, how can i subscribe for a blog web site? The account helped me a acceptable deal.
    I were a little bit familiar of this your broadcast offered brilliant transparent
    concept

  30. Hi there would you mind letting me know which web host you’re working with?
    I’ve loaded your blog in 3 completely different internet browsers and I must say this blog loads a lot faster then most.
    Can you suggest a good web hosting provider at a honest price?
    Many thanks, I appreciate it!

  31. I believe everybody went like Ones New website, reason being things like this site without doubt has a article on quality. I loved read A New content. go on To remain a useful article, I will avail Once more by One additional time. Bless you.

  32. Today, I went to the beach front with my kids. 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
    put 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!

  33. I was suggested this blog by my cousin. I’m not sure whether this post is written by him as no one
    else know such detailed about my difficulty. You’re amazing!
    Thanks!

  34. Hey! Do you know if they make any plugins to protect against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard
    on. Any recommendations?

  35. This design is incredible! You most certainly know how to keep a reader amused.

    Between your wit and your videos, I was almost moved to start my own blog
    (well, almost…HaHa!) Excellent job. I really enjoyed what
    you had to say, and more than that, how you presented it.
    Too cool!

  36. Have you ever thought about adding a little bit more than just your articles?
    I mean, what you say is fundamental and all. Nevertheless think
    of if you added some great graphics or video clips to give your posts more, “pop”!
    Your content is excellent but with pics and videos, this website could certainly be one of
    the greatest in its niche. Terrific blog!

  37. Hello would you mind sharing which blog platform you’re working
    with? I’m planning to start my own blog in the near future but I’m having a difficult time making a decision 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 completely unique. P.S
    Sorry for getting off-topic but I had to ask!

  38. It’s a pity you don’t have a donate button!
    I’d most certainly donate to this fantastic blog!
    I guess for now i’ll settle for bookmarking and adding your
    RSS feed to my Google account. I look forward to
    new updates and will share this site with my Facebook group.
    Talk soon!

  39. Definitely believe that which you stated. Your favorite justification seemed to be on the internet the easiest thing
    to be aware of. I say to you, I definitely get irked while
    people consider worries that they just do not know about.
    You managed to hit the nail upon the top and defined out the whole thing without having side effect , people could take
    a signal. Will probably be back to get more. Thanks

  40. I was wondering if you ever considered changing the structure
    of your blog? Its very well written; I love what youve
    got to say. But maybe you could a little more in the way of content so people could connect with it better.
    Youve got an awful lot of text for only having 1
    or two pictures. Maybe you could space it out better?

  41. Excellent post. I was checking constantly this blog and I am impressed!
    Extremely useful info specially the remaining part 🙂 I deal with such info much.
    I was seeking this particular information for a long time.
    Thank you and best of luck.

  42. Hello There. I found your blog using msn. This is a very well
    written article. I will be sure to bookmark it and come back to read more of your useful information. Thanks for the post.

    I’ll certainly return.

  43. It¦s really a nice and helpful piece of info. I am satisfied that you just shared this useful information with us. Please keep us up to date like this. Thanks for sharing.

Leave a Reply to plenty of fish dating site Cancel reply

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