爵士OIer查看:1 回复:5 评论:1 创建时间:2021-02-16T17:17:15用户:爵士OIer查看:1 回复:5 评论:1 创建时间:2021-02-16T17:17:15
这边想要恢复2019年下半年Max等人和2020年爵士等人的算法、数据结构的研究和普及。
因为是串讲所以各种问题、数据结构对比都会出现，结构稍乱但是内容无水分。
我们来看看几个经典的问题加深数据结构的认识。
这次我们着手解决两个经典问题。
目录
1. 最大子段和
2. 异或、查和
序列最大子段和（SP1043）
最大子段和是非常经典的一个问题，算法多种多样，但是我们需要支持多次查询，这怎么办？
很明显这里元素肯定有负数也有正数，否则就是整个序列。
各种朴素算法显然是不行了。我们用分治算法思考。
看上面这张图。假设我们已经分别求出了红色段和蓝色段的“应求”的量，如何合并这些信息，解出整一段的“应求”的量？
很显然，如果两个区间连续子段和能够合并，则这些字段和必须包含该段区间的左端点或右端点。因此这样，我们需要维护：
1. 包含左端点的最大子段和
2. 包含右端点的最大子段和
3. 整段区间的和
我们最后需要查询整个序列的最大子段和，因此递归分治地求解出上述三个信息之后，取三者最大值即可。
我们能够找到一种数据结构，能够快速分治地维护上述三个信息？
没错，线段树！
我们甚至不需要考虑如何修改，因为这里只需要支持查询。
然后略微改一下线段树的板子就行啦qaqqq
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const ll SIZE=50005;
struct Tree{ll l,r,sum,lmax,rmax,dat;}t[SIZE*4];
ll n,m,a[SIZE];
void Build(ll p,ll l,ll r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].dat=a[l],t[p].sum=a[l];
t[p].lmax=a[l],t[p].rmax=a[l];
return;
}
ll mid=l+r>>1;
Build(p*2,l,mid);
Build(p*2+1,mid+1,r);
//回溯时统计每段区间的三个值
t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
t[p].rmax=max(t[p*2].rmax+t[p*2+1].sum,t[p*2+1].rmax);
t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
}
Tree Query(ll p,ll l,ll r){
//如果节点代表区间被查询区间覆盖，直接返回
if(l<=t[p].l&&r>=t[p].r)return t[p];
ll mid=t[p].l+t[p].r>>1;
//如果不包含整个区间，左右分别递归
if(r<=mid)return Query(p*2,l,r);
if(l>mid)return Query(p*2+1,l,r);
//如果查询区间被节点代表区间覆盖，左右一起递归，求解返回
else{
Tree ans,a,b;
a=Query(p*2,l,r),b=Query(p*2+1,l,r);
ans.sum=a.sum+b.sum;
ans.dat=max(max(a.dat,a.rmax+b.lmax),b.dat);
ans.lmax=max(a.lmax,a.sum+b.lmax);
ans.rmax=max(b.rmax,b.sum+a.rmax);
return ans;
}
}
int main(){
n=read();
for(register ll i=1;i<=n;i++)a[i]=read();
Build(1,1,n);
m=read();
while(m--){
ll l=read(),r=read();
printf("%lld\n",Query(1,l,r).dat);
}
return 0;
}
区间异或，区间查和（CF242E）
区间异或区间查和也是非常经典的问题。
这里异或是二进制下按位异或。法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）。
因此我们拆位线段树。将每一个数拆20位即可。
实际上是20棵线段树，每一棵维护一位。
主函数
我们一部分一部分看代码。
主函数如下：
int main(){
n=read(),b[0]=1;
for(int i=1;i<30;i++)b[i]=b[i-1]*2;
for(int i=1;i<=n;i++)a[i]=read();
build(1,1,n),m=read();
while(m--){
int opt=read();
if(opt==1){
int lt=read(),rt=read();
printf("%lld\n",ask(1,1,n,lt,rt));
}
else{
int lt=read(),rt=read(),x=read();
for(int i=0;i<21;i++)
if((x>>i)&1)change(1,1,n,lt,rt,i);
}
}
return 0;
}
其中b数组是2的k次方，build是线段树建树。
大家可以看到我们拆位的部分：
for(int i=0;i<21;i++) if((x>>i)&1)change(1,1,n,lt,rt,i);
线段树建树
现在看我们的建树部分。
//拆位，实际上是20棵线段树，每一棵维护一位
void build(int p,int l,int r){
if(l>r)return;
if(l==r){
int w=a[l];
for(int i=0;i<21;i++)
if((w>>i)&1)t[p][i]=1;
return;
}
int mid=l+r>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
for(int i=0;i<21;i++)t[p][i]=t[p*2][i]+t[p*2+1][i];
return;
}
延迟标记
接下来我们涉及延迟标记怎么打的问题。
因为是20棵线段树，所以我们每一位都需要打一次懒标记。
简单地说，懒标记函数里需要有参数表示哪一位。
之后就是区间取反了。
1. 懒标记只需^=1。
2. 查询的和val需要拿总长度减去原本的val，因为这里是每一位都一棵线段树，维护的是1的个数。
这样代码就好写啦qaq
void pushdown(int p,int l,int r,int w){
t[p][w]=(r-l+1)-t[p][w];
if(l!=r)tag[p*2][w]^=1,tag[p*2+1][w]^=1;
tag[p][w]=0;
}
查询、修改
那么接下来查询、修改就很简单啦qaqq
修改代码如下：
//修改
void change(int p,int l,int r,int lt,int rt,int w){
if(tag[p][w])pushdown(p,l,r,w);
if(r<lt||rt<l)return;
if(lt<=l&&r<=rt){pushdown(p,l,r,w);return;}
int mid=l+r>>1;
change(p*2,l,mid,lt,rt,w);
change(p*2+1,mid+1,r,lt,rt,w);
t[p][w]=t[p*2][w]+t[p*2+1][w];
}
查询代码如下:
//查询
ll ask(int p,int l,int r,int lt,int rt){
for(int i=0;i<21;i++)
if(tag[p][i])pushdown(p,l,r,i);
if(r<lt||rt<l)return 0;
if(lt<=l&&r<=rt){
ll sum=0;
for(int i=0;i<=20;i++)sum+=t[p][i]*b[i];
return sum;
}
int mid=l+r>>1;
ll s1=ask(p*2,l,mid,lt,rt);
ll s2=ask(p*2+1,mid+1,r,lt,rt);
return s1+s2;
}
结语
今天的教程就到这里了。
我们解决了两个经典问题：
1. 维护区间最大子段和
2. 区间异或，区间查和
