Article From:https://www.cnblogs.com/smyjr/p/9739276.html

Transmission gate

XOR maxima should be used.\(trie\)Trees, greedy from high to low, though the number of questions asked here should be added.\(x\),But this idea can still be used.

From high to low, we need to find a plus.\(x\)Post current binary digit\(j\)Not equal to\(b\)The number of current bits\(b\)The current position is 0, so we need to find a number now.\(x\)Post current position\(j\)For 1, the number chosen before the record is\(ans\),Then we’ll have to find one.\([ans+(1<<j)-x,ans+(1<<j)-(1<<j)-1-x]\)The number of intervals; if\(b\)The current bit is 1, so the value range is\([ans-x,ans-(1<<j)-1-x]\).If there is this number, then\(ans\)Current position\(j\)Can be equal to\(b\)Current position\(xor\ 1\),Otherwise, the other way round.

This operation can be implemented by using the chairman tree to query the number of occurrences of an interval.

#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define eps (1e-7)

using namespace std;
const int N=500000+10;
const LL inf=1ll<<45;
il LL rd()
{
  re LL x=0,w=1;re char ch=0;
  while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
  return x*w;
}

#define mid ((l+r)>>1)

int s[N*20],ch[N*20][2],rt[N],tt;
int n,m,kk,L,R,a[N];
il void inst(int p)
{
  rt[p]=++tt;
  int o1=rt[p],o2=rt[p-1],l=0,r=n;
  s[o1]=s[o2]+1;
  do
    {
      if(a[p]<=mid)
    {
      ch[o1][0]=++tt,ch[o1][1]=ch[o2][1];
      o1=ch[o1][0],o2=ch[o2][0],r=mid;
    }
      else
    {
      ch[o1][0]=ch[o2][0],ch[o1][1]=++tt;
      o1=ch[o1][1],o2=ch[o2][1],l=mid+1;
    }
      s[o1]=s[o2]+1;
    }
  while(l<r);
}
int quer(int o1,int o2,int l,int r,int ll,int rr)
{
  if(ll<=l&&r<=rr) return s[o1]-s[o2];
  int an=0;
  if(ll<=mid) an+=quer(ch[o1][0],ch[o2][0],l,mid,ll,rr);
  if(rr>mid) an+=quer(ch[o1][1],ch[o2][1],mid+1,r,ll,rr);
  return an;
}
bool ok(int l,int r,int ll,int rr)
{
  ll=max(ll,0),rr=min(rr,n);
  return ll<=rr?quer(rt[r],rt[l-1],0,n,ll,rr):0;
}
int q;

int main()
{
  ///no O2
  m=rd(),q=rd();
  for(int i=1;i<=m;i++) n=max(n,a[i]=rd());
  for(int i=1;i<=m;i++) inst(i);
  while(q--)
    {
      int b=rd(),x=rd(),ll=rd(),rr=rd(),ans=0;
      for(int i=17;i>=0;i--)
        {
          int nw=ans|(((b>>i&1)^1)<<i);
          if(ok(ll,rr,nw-x,nw+(1<<i)-1-x)) ans=nw;
          else ans|=(b>>i&1)<<i;
        }
      printf("%d\n",ans^b);
    }
  return 0;
}
Link of this Article: Luogu P3293 [SCOI2016] delicious

Leave a Reply

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