BZOJ5312：冒险——题解-白红宇

BZOJ5312：冒险——题解

阅读量：6578 次

发布时间：2019-06-24

本文共 2568 字，大约阅读时间需要 8 分钟。

Kaiser终于成为冒险协会的一员，这次冒险协会派他去冒险，他来到一处古墓，却被大门上的守护神挡住了去路，守护神给出了一个问题，只有答对了问题才能进入，守护神给出了一个自然数序列a,每次有一下三种操作。

1，给出l,r,x，将序列l,r之间的所有数都 and x

2，给出l,r,x，将序列l,r之间的所有数都 or x

3，给出l,r，询问l,r之间的最大值

（下划线以前都是废话）

没有什么好方法，因为最大值的变化不能用简单的and x以及or x，但是我们能够暴力线段树维护，然而毫无疑问是TLE。

于是我们的目标是直接能够mx[a]and/or=x以此维护。

我们考虑能不能用吉司机线段树维护一下。

让我们想一个naive的想法，即我and x则区间全变成x，or x则区间全变成x。

于是我们需要多记录两个区间and值和区间or值，如果区间and值and x=x则我们全变x，如果区间or值or x=x则我们全变x。

当然会TLE……

————————————————————————

我们继续想，区间内的数在经过多次操作后其公共的1的数量占每个数的1的个数的比重会越来越大并最终为100%。

于是我们要利用这个想法，当然这里给出结论：(区间or值xor区间and值)and x=0时我们更新。

（括号内的东西代表了各数的不公有的1，也就是说x不能有它们不公有的1，剩下的还请读者自行推导其正确性。）

此时mx[a]and/or=x即可（显然的），同时我们还可对区间and值和or值也and/or=x来更新（不显然，但懒得证了）。

现在就很像吉司机线段树了，但是对于势能分析我要写个大大的坑字在这里。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int INF=(1<<21)-1;const int N=2e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int n,m,b[N],mx[N*4],ran[N*4],ror[N*4],lza[N*4],lzo[N*4];inline void upt(int a){ mx[a]=max(mx[a<<1],mx[a<<1|1]); ran[a]=ran[a<<1]&ran[a<<1|1]; ror[a]=ror[a<<1]|ror[a<<1|1];}void build(int a,int l,int r){ lza[a]=INF,lzo[a]=0; if(l==r){ mx[a]=b[l];ran[a]=b[l];ror[a]=b[l]; return; } int mid=(l+r)>>1; build(a<<1,l,mid);build(a<<1|1,mid+1,r); upt(a);}inline void push(int a){ int ls=a<<1,rs=a<<1|1; if(lzo[a]!=0){ mx[ls]|=lzo[a];mx[rs]|=lzo[a]; ran[ls]|=lzo[a];ran[rs]|=lzo[a]; ror[ls]|=lzo[a];ror[rs]|=lzo[a]; lza[ls]|=lzo[a];lza[rs]|=lzo[a]; lzo[ls]|=lzo[a];lzo[rs]|=lzo[a]; lzo[a]=0; } if(lza[a]!=INF){ mx[ls]&=lza[a];mx[rs]&=lza[a]; ran[ls]&=lza[a];ran[rs]&=lza[a]; ror[ls]&=lza[a];ror[rs]&=lza[a]; lza[ls]&=lza[a];lza[rs]&=lza[a]; lza[a]=INF; }}void mdy(int a,int l,int r,int l1,int r1,int x,bool k){ if(r
                
                 
                  >1; push(a); mdy(a<<1,l,mid,l1,r1,x,k);mdy(a<<1|1,mid+1,r,l1,r1,x,k); upt(a);}int qry(int a,int l,int r,int l1,int r1){ if(r
                  
                   
                    >1; push(a); return max(qry(a<<1,l,mid,l1,r1),qry(a<<1|1,mid+1,r,l1,r1));}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)b[i]=read(); build(1,1,n); while(m--){ int op=read(),x=read(),y=read(); if(op==1)mdy(1,1,n,x,y,read(),0); if(op==2)mdy(1,1,n,x,y,read(),1); if(op==3)printf("%d\n",qry(1,1,n,x,y)); } return 0;}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/9156931.html

你可能感兴趣的文章