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

50 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. Wow, awesome weblog format! How long have you been running a
    blog for? you made blogging glance easy.
    The total look of your website is magnificent, let
    alone the content material!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注