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

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

发表评论

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