BZOJ5312：冒险—

https://www.lydsy.com/JudgeOnline/problem.php?id=5312

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<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int INF=(<<)-;

const int N=2e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

int n,m,b[N],mx[N*],ran[N*],ror[N*],lza[N*],lzo[N*];

inline void upt(int a){

    mx[a]=max(mx[a<<],mx[a<<|]);

    ran[a]=ran[a<<]&ran[a<<|];

    ror[a]=ror[a<<]|ror[a<<|];

}

void build(int a,int l,int r){

    lza[a]=INF,lzo[a]=;

    if(l==r){

    mx[a]=b[l];ran[a]=b[l];ror[a]=b[l];

    return;

    }

    int mid=(l+r)>>;

    build(a<<,l,mid);build(a<<|,mid+,r);

    upt(a);

}

inline void push(int a){

    int ls=a<<,rs=a<<|;

    if(lzo[a]!=){

    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]=;

    }

    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<l1||r1<l)return;

    if(l1<=l&&r<=r1&&(!((ran[a]^ror[a])&x))){

    if(!k){mx[a]&=x;ran[a]&=x;ror[a]&=x;lza[a]&=x;}

    else{mx[a]|=x;ran[a]|=x;ror[a]|=x;lza[a]|=x;lzo[a]|=x;}

    return;

    }

    int mid=(l+r)>>;

    push(a);

    mdy(a<<,l,mid,l1,r1,x,k);mdy(a<<|,mid+,r,l1,r1,x,k);

    upt(a);

}

int qry(int a,int l,int r,int l1,int r1){

    if(r<l1||r1<l)return -;

    if(l1<=l&&r<=r1)return mx[a];

    int mid=(l+r)>>;

    push(a);

    return max(qry(a<<,l,mid,l1,r1),qry(a<<|,mid+,r,l1,r1));

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++)b[i]=read();

    build(,,n);

    while(m--){

    int op=read(),x=read(),y=read();

    if(op==)mdy(,,n,x,y,read(),);

    if(op==)mdy(,,n,x,y,read(),);

    if(op==)printf("%d\n",qry(,,n,x,y));

    }

    return ;

}

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

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

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

巴特西

BZOJ5312：冒险——题解

最新文章

热门文章