loj#6507. 「雅礼集训 2018 Day7」A 解题报告

解题报告

loj#6507. 「雅礼集训 2018 Day7」A解题报告：

题意

给定一个长为 $n$ 的序列，$q$ 次操作，支持区间或，区间与，区间求最小值。（$1\leqslant n,q\leqslant 5\times 10^5$）

分析

线段树+势能分析。

考虑线段树每个结点记录区间的与值 $vand$，或值 $vor$，最小值 $minn$，然后分类讨论。

与 $x$ 操作：

• 如果 $x$ 与整个区间不会有改变，即 $vor\subseteq x$，那么直接返回；
• 如果 $x$ 与整个区间会让区间直接推平，即 $vor\ \text{and}\ x=vand\ \text{and}\ x$，那么打标记；
• 否则暴力递归。

或 $x$ 操作：

• 如果 $x$ 或整个区间不会有改变，即 $x\subseteq vand$，那么直接返回；
• 如果 $x$ 或整个区间会让区间直接推平，即 $vor\ \text{or}\ x=vand\ \text{or}\ x$，那么打标记；
• 否则暴力递归。

有一个小问题，为什么第二种情况可以这样判，比如如果与操作的时候有某一位 $x$ 没有，可是这个区间的这一位并不相同，那这样不就有问题吗？但是这种情况这些位置都会变成 $0$。（是不是只有我有这么傻逼的问题）

我们想一想怎么证明复杂度。

如果当前递归到了操作区间内，那么一次操作会产生的影响：让区间若干个不同色位集体变成同色，或者集体某一位异或 $1$，第二种情况小号的复杂度应该与第一种情况是一致的，第一种情况的复杂度应该是 $O(n\log^2 n)$，所以复杂度是两个 $\log$ 的。

代码

《15min rush 2k 代码》

#include<stdio.h>
#define lc(x) (x)<<1
#define rc(x) (x)<<1|1
const int maxn=500005,maxt=maxn<<2,inf=2147483647;
int n,m;
int a[maxn],vand[maxt],vor[maxt],minn[maxt],lazy[maxt];
inline int min(int a,int b){
    return a<b? a:b;
}
inline void pushup(int now){
    vand[now]=vand[lc(now)]&vand[rc(now)];
    vor[now]=vor[lc(now)]|vor[rc(now)];
    minn[now]=min(minn[lc(now)],minn[rc(now)]);
}
inline void getlazy(int now,int v){
    vand[now]=vor[now]=minn[now]=lazy[now]=v;
}
inline void pushdown(int now){
    if(lazy[now]!=-1)
        getlazy(lc(now),lazy[now]),getlazy(rc(now),lazy[now]),lazy[now]=-1;
}
void build(int l,int r,int now){
    lazy[now]=-1;
    if(l==r){
        getlazy(now,a[l]);
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc(now)),build(mid+1,r,rc(now));
    pushup(now);
}
void updateand(int l,int r,int now,int L,int R,int v){
    if((vor[now]&v)==vor[now])
        return ;
    if(L<=l&&r<=R&&(vor[now]&v)==(vand[now]&v)){
        getlazy(now,vor[now]&v);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(L<=mid)
        updateand(l,mid,lc(now),L,R,v);
    if(mid<R)
        updateand(mid+1,r,rc(now),L,R,v);
    pushup(now);
}
void updateor(int l,int r,int now,int L,int R,int v){
    if((vand[now]|v)==vand[now])
        return ;
    if(L<=l&&r<=R&&(vand[now]|v)==(vor[now]|v)){
        getlazy(now,vand[now]|v);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(L<=mid)
        updateor(l,mid,lc(now),L,R,v);
    if(mid<R)
        updateor(mid+1,r,rc(now),L,R,v);
    pushup(now);
}
int query(int l,int r,int now,int L,int R){
    if(L<=l&&r<=R)
        return minn[now];
    int mid=(l+r)>>1,res=inf;
    pushdown(now);
    if(L<=mid)
        res=min(res,query(l,mid,lc(now),L,R));
    if(mid<R)
        res=min(res,query(mid+1,r,rc(now),L,R));
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int opt,l,r,v;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            scanf("%d",&v);
            updateand(1,n,1,l,r,v);
        }
        if(opt==2){
            scanf("%d",&v);
            updateor(1,n,1,l,r,v);
        }
        if(opt==3)
            printf("%d\n",query(1,n,1,l,r));
    }
    return 0;
}