「SCOI2016」美味 解题报告

「SCOI2016」美味

状态极差无比，一个锤子题目而已

考虑每次对\(b\)和\(d\)求\(c=d \ xor \ (a+b)\)的最大值，因为异或每一位是独立的，所以我们可以尝试按位贪心。

如果要求\(c\)的从低到高第\(i\)位为\(0\)(最低位为第\(0\)位)，那么此时\(c\)的更高位是确定好的了

\[\_\_\_\_\_\_\_01111111\\
\_\_\_\_\_\_\_00000000
\]

这是\(c\)的上界和下界，分别减去\(b\)后，得到\(a\)需要满足的区间，然后在原位置区间里面查询\(a\)需要满足的值域区间，直接主席树即可

然后如果要求此位为\(1\)

\[\_\_\_\_\_\_\_11111111\\
\_\_\_\_\_\_\_10000000
\]

可以看出刚好是把值域分完了的，所以这样是对的

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

using std::min;

using std::max;

const int N=2e5+10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,m,M=1e5;

int root[N],sum[N*25],tot,ch[N*25][2];

#define ls ch[now][0]

#define rs ch[now][1]

#define ols ch[las][0]

#define ors ch[las][1]

void rebuild(int las,int &now,int l,int r,int p)

{

    now=++tot;

    if(l==r) {sum[now]=sum[las]+1;return;}

    int mid=l+r>>1;

    if(p<=mid) rebuild(ols,ls,l,mid,p),rs=ors;

    else ls=ols,rebuild(ors,rs,mid+1,r,p);

    sum[now]=sum[ls]+sum[rs];

}

int query(int now,int L,int R,int l,int r)

{

    if(l>r) return 0;

    if(l==L&&r==R) return sum[now];

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return query(ls,L,Mid,l,Mid)+query(rs,Mid+1,R,Mid+1,r);

}

int main()

{

	read(n),read(m);

	for(int a,i=1;i<=n;i++) read(a),rebuild(root[i-1],root[i],1,M,a);

	for(int b,x,l,r,lp,rp,c,i=1;i<=m;i++)

	{

		read(b),read(x),read(lp),read(rp);

		c=0;

		for(int j=17;~j;j--)

		{

			if(b>>j&1) l=c-x,r=c-x+(1<<j)-1;

			else l=c-x+(1<<j),r=c-x+(1<<j+1)-1;

			l=max(l,1),r=min(r,M);

			if(query(root[rp],1,M,l,r)-query(root[lp-1],1,M,l,r)) c|=(!(b>>j&1))<<j;

			else c|=(b>>j&1)<<j;

		}

		printf("%d\n",c^b);

	}

	return 0;

}

---

2019.3.5