【线段树】P7492

· · 题解

Tips

本题简单版为 P4513。如果您已经完成了那题，可以跳过第一部分。

时间有限，图画的不是特别规整，但还比较清晰，有助于理解。

Solution

Part I 信息维护

本题要求区间修改、区间查询，容易想到要使用线段树。但是线段树直接维护最大子段和不好维护，上传时会遇到困难。我们需要一些辅助信息。

可以尝试从 push_up 函数或分治的角度找出合并时需要的信息。假设我们已经维护出了两个子区间内的需要的信息，按下图讨论：

分类讨论，若新子段和没有跨越两个子区间（即只在其中一个区间，如上图情况一，蓝色部分），则此时最大子段和为两区间的最大字段和的较大者。

若跨越了两个区间，此时由左区间后缀和右区间前缀拼接而成（如上图情况二，绿色部分）。既然要求最大，那么应该是左区间最大后缀 suf_r 和右区间最大前缀 pre_r。

最终答案为上图两段蓝色和一段绿色中的最大值。可写出式子 ans=\max\{ans_l,ans_r,suf_l+pre_r\}。

在上述过程中，我们还使用到了最大前、后缀，也需要进行维护。

以最大前缀为例，如下图：

分类讨论，可能只取左区间一部分，此时合并后最大前缀即为左区间最大前缀 pre_l。也有可能跨越了整个左区间，此时最大前缀为左区间和 sum_l 加上右区间最大前缀 pre_r。可写出式子 pre=\max\{pre_l,sum_l+pre_r\}。

最大后缀同理。但是在过程中使用到了区间和，也需要维护一下。

至此我们完成了信息维护部分。

完成后 push_up 函数代码：

void push_up(int id){
    sum[id]=sum[id<<1]+sum[id<<1|1];
    ans[id]=max({ans[id<<1],ans[id<<1|1],suf[id<<1]+pre[id<<1|1]});
    pre[id]=max(pre[id<<1],sum[id<<1]+pre[id<<1|1]);
    suf[id]=max(suf[id<<1|1],sum[id<<1|1]+suf[id<<1]);
}

Part II 修改

按位或操作不太方便使用懒标记记录，那就无法直接进行区间修改，只能进行单点修改。

但是容易发现按位或有一些性质可以使用。

设 f(x) 为 x 中二进制位 1 的个数。那么每次按位或后，f(x) 只会增大或不变。由于 -2^{30}\leq a_i,k<2^{30}，那么这个数最多只有 30 个二进制位。也就是说，最多只有 30 次有效按位或操作（指对其有影响的操作）。

我们可以再维护一下每个区间的按位与和。当一个区间的按位与和值 p 满足 p \operatorname{and} k=k 时，k 中所有为 1 的二进制位在该区间的每一个数中均为 1，这样的操作对所有数都没有影响，就不需要递归到这个区间中。

我们已经完成了本题，总时间复杂度 O(n\log n \log a)，可以通过本题。

Part III 总结

本题使用了无懒标记的单点修改线段树，需要维护区间和、区间最大前缀、区间最大后缀、区间最大子段和。

主要还是思维，在线段树题目中相对代码难度不高。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
long long n,m,a[maxn],ans[maxn],pre[maxn],suf[maxn],sum[maxn],ad[maxn];
void push_up(int id){
    sum[id]=sum[id<<1]+sum[id<<1|1];
    ans[id]=max({ans[id<<1],ans[id<<1|1],suf[id<<1]+pre[id<<1|1]});
    pre[id]=max(pre[id<<1],sum[id<<1]+pre[id<<1|1]);
    suf[id]=max(suf[id<<1|1],sum[id<<1|1]+suf[id<<1]);
    ad[id]=ad[id<<1]&ad[id<<1|1];
}
void build(int l,int r,int id){
    if(l==r){
        ans[id]=pre[id]=suf[id]=max(0ll,a[l]);
        ad[id]=sum[id]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
    push_up(id);
}
void update(int l,int r,int s,int t,int id,long long num){
    if(s==t){
        ad[id]|=num;sum[id]|=num;
        ans[id]=pre[id]=suf[id]=max(0ll,sum[id]);
        return;
    }
    int mid=s+t>>1;
    if(l<=mid && ((ad[id<<1] & num) !=num)) update(l,r,s,mid,id<<1,num);
    if(r>mid && ((ad[id<<1|1] & num) !=num)) update(l,r,mid+1,t,id<<1|1,num);
    push_up(id);
}
struct node{
    long long a,p,s,sm;
};
node mg(node xx,node yy){
    node ret;
    ret.sm=xx.sm+yy.sm;
    ret.a=max({xx.a,yy.a,xx.s+yy.p});
    ret.p=max(xx.p,xx.sm+yy.p);
    ret.s=max(yy.s,yy.sm+xx.s);
    return ret;
}
node qry(int l,int r,int s,int t,int id){
    if(s>=l && t<=r){
        return {ans[id],pre[id],suf[id],sum[id]};
    }
    int mid=s+t>>1;
    if(l<=mid && r>mid) return mg(qry(l,r,s,mid,id<<1),qry(l,r,mid+1,t,id<<1|1));
    else if(l<=mid) return qry(l,r,s,mid,id<<1);
    else if(r>mid) return qry(l,r,mid+1,t,id<<1|1);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    for(int i=1;i<=m;i++){
        long long op,x,y,z;
        cin>>op>>x>>y;
        if(op==1){
            cout<<qry(x,y,1,n,1).a<<"\n";
        }
        else{
            cin>>z;
            update(x,y,1,n,1,z);
        }
    }
    return 0;
}

AC record