洛谷P3293 [SCOI2016]美味（主席树）

据说这题做法叫做可持久化trie树？（然而我并不会）

首先考虑一下贪心，从高位到低位枚举，如果能选1肯定比选0优

假设已经处理到了$b$的第$i$位，为1（为0的话同理就不说了）

那么只有当$a_j+x$的第$i$位为0时才能让答案的第$i$位为$1$

考虑把$x$的影响去掉。如果当前的答案是$ans$（即令前面几位贪心情况下最大且第$i$位为0时的$a$），那么只有在区间$[ans-x,ans+(1<<i)-1-x]$的数能在加上$x$之后第$i$位为0（这个可以自己手动算一算）

如果存在，那么$ans$第$i$位变为0（存在前$i$位与之相同且第$i$位为0的$a_i$），否则变为1（只存在前$i$位与之相同且第$i$位为0的$a_i$）

然后查找是两个区间限制主席树套上去就好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=2e5+,M=N*;

 int rt[N],L[M],R[M],sum[M],a[N],cnt,n,q,m;

 void update(int &now,int last,int x,int l=,int r=m){

     sum[now=++cnt]=sum[last]+;

     if(l==r) return;

     int mid=(l+r)>>;

     if(x<=mid) R[now]=R[last],update(L[now],L[last],x,l,mid);

     else L[now]=L[last],update(R[now],R[last],x,mid+,r);

 }

 int query(int u,int v,int ql,int qr,int l=,int r=m){

     if(ql<=l&&qr>=r) return sum[u]-sum[v];

     int mid=(l+r)>>;

     if(ql<=mid&&query(L[u],L[v],ql,qr,l,mid)) return ;

     if(qr>mid&&query(R[u],R[v],ql,qr,mid+,r)) return ;

     return ;

 }

 inline int find(int u,int v,int ql,int qr){

     cmax(ql,),cmin(qr,m);

     if(ql>qr) return ;

     return query(rt[u],rt[v],ql,qr);

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),q=read();

     for(int i=;i<=n;++i) cmax(m,a[i]=read());

     for(int i=;i<=n;++i)

     update(rt[i],rt[i-],a[i]);

     while(q--){

         int b=read(),x=read(),ql=read(),qr=read(),ans=;

         for(int i=;i>=;--i){

             int now=ans+((^((b>>i)&))<<i);

             if(find(ql-,qr,now-x,now+(<<i)--x)) ans=now;

             else ans+=((b>>i)&)<<i;

         }

         print(ans^b);

     }

     Ot();

     return ;

 }

巴特西

洛谷P3293 [SCOI2016]美味（主席树）

最新文章

热门文章