SPOJ GSS 线段树系列

给出序列，查询区间的最大子段和。

• 维护最大前缀子段和，最大后缀子段和，区间答案即可
• 区间合并的时候，大区间的答案只能是左区间答案，右区间答案，左后缀+右前缀三者最大值
• 查询过程可以返回node，重载 + 来合并答案

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 5e5+10;
const int mx = 40;
const ll mod = 998244353;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定序列 q次询问 每次询问一个区间内的最大子段和
//记录答案 区间第一个数开始的最大子段和  区间最后一个数结尾的最大子段和  区间合并
int n,m;
int a[maxn];
int sum[maxn];//前缀和
struct node 
{int l,r;int ans,pre,suf;node operator + (const node &f)const {node t;t.ans=max(max(ans,f.ans),suf+f.pre);t.pre=max(pre,sum[r]-sum[l-1]+f.pre);//不加入/加入右区间的影响  t.suf=max(f.suf,suf+sum[f.r]-sum[f.l-1]);t.l=l,t.r=f.r;return t;}
}tree[maxn<<2];
inline void pushup(int rt) 
{tree[rt]=tree[lc]+tree[rc];
}
inline void build(int rt,int l,int r) 
{tree[rt].l=l,tree[rt].r=r;if(l == r) {int d=a[l];tree[rt].pre=tree[rt].suf=tree[rt].ans=d;return ;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(rt);
}
inline node query(int rt,int vl,int vr) 
{int l=tree[rt].l,r=tree[rt].r;if(vl<=l && r<=vr) return tree[rt];int mid=l+r>>1;if(vr<=mid) return query(lc,vl,vr);else if(vl > mid) return query(rc,vl,vr);return query(lc,vl,vr)+query(rc,vl,vr);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=n;i++) sum[i] = a[i]+sum[i-1];build(1,1,n);scanf("%d",&m);while(m--) {int l,r;scanf("%d %d",&l,&r);printf("%d\n",query(1,l,r).ans);}return 0;
}

和1类似，只不过多了个单点修改的操作。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 5e4+10;
const int mx = 40;
const ll mod = 998244353;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
struct node 
{ll ans,pre,suf,sum;int l,r;node operator + (const node &f)const {node t;t.ans=max(suf+f.pre,max(ans,f.ans));t.pre=max(pre,sum+f.pre);t.suf=max(f.suf,f.sum+suf);t.sum=sum+f.sum;t.l=l,t.r=f.r;return t;}
}tree[maxn<<2];
inline void pushup(int rt) 
{tree[rt]=tree[lc]+tree[rc];
}
void build(int rt,int l,int r) 
{tree[rt].l=l,tree[rt].r=r;if(l == r) {scanf("%lld",&tree[rt].ans);tree[rt].pre=tree[rt].suf=tree[rt].sum=tree[rt].ans;return ;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(rt);
}
inline void upd(int rt,int pos,int v) 
{int l=tree[rt].l,r=tree[rt].r;if(l==r) {tree[rt].sum=tree[rt].ans=v;tree[rt].pre=tree[rt].suf=v;return ;}int mid=l+r>>1;if(pos<=mid) upd(lc,pos,v);else upd(rc,pos,v);pushup(rt);
}
inline node query(int rt,int vl,int vr) 
{int l=tree[rt].l,r=tree[rt].r;if(vl<=l && r<=vr) return tree[rt];int mid=l+r>>1;if(vr<=mid) return query(lc,vl,vr);else if(vl>mid) return query(rc,vl,vr);return query(lc,vl,vr)+query(rc,vl,vr);
}
int n,m;
int main()
{scanf("%d",&n);build(1,1,n);scanf("%d",&m);while(m--) {int f,x,y;scanf("%d %d %d",&f,&x,&y);if(!f) {upd(1,x,y);}else printf("%lld\n",query(1,x,y).ans);}return 0;
}

• 区间每个数开根号，经典的单点暴力修改，每个点只能被修改log次。
• 记录最大值，如果最大值小于等于1，剪枝。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 1e5+10;
const int mx = 40;
const ll mod = 998244353;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//区间每个数开方 区间求和 记录最大值 暴力单点修改
struct node 
{int l,r;ll mmax,sum;node operator + (const node &f)const{node t;t.mmax=max(mmax,f.mmax);t.sum=sum+f.sum;t.l=l,t.r=f.r;return t;} 
}tree[maxn<<2];
inline void pushup(int rt)
{tree[rt]=tree[lc]+tree[rc];
}
inline void build(int rt,int l ,int r)
{tree[rt].l=l,tree[rt].r=r;if(l==r) {scanf("%lld",&tree[rt].sum);tree[rt].mmax=tree[rt].sum;return ;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(rt);
}
inline void upd(int rt,int vl,int vr) 
{int l=tree[rt].l,r=tree[rt].r;if(tree[rt].mmax <= 1 ||  l > vr || r<vl) return;//剪枝if(l == r) {ll d=(ll)sqrt(tree[rt].mmax);//    cout<<"--"<<tree[rt].mmax<<' '<<d<<'\n';tree[rt].mmax=tree[rt].sum=d;return ;}int mid=l+r>>1;upd(lc,vl,vr);upd(rc,vl,vr);pushup(rt);
}
inline node query(int rt,int vl,int vr)
{int l=tree[rt].l,r=tree[rt].r;if(vl<=l && r<=vr) return tree[rt];int mid=l+r>>1;if(vr<=mid) return query(lc,vl,vr);else if(vl>mid) return query(rc,vl,vr);return query(lc,vl,vr)+query(rc,vl,vr);
}
int n,cnt,m;
int main()
{while(~scanf("%d",&n)) {build(1,1,n);scanf("%d",&m);printf("Case #%d:\n",++cnt);while(m--){int f,x,y;scanf("%d %d %d",&f,&x,&y);if(x>y) swap(x,y);if(!f) {upd(1,x,y);}else printf("%lld\n",query(1,x,y).sum);}puts("");}return 0;
}

• 这题咋一看很麻烦，但如果能从分类讨论的方向着手，会发现其实就是在第一题的基础上加了点东西。我们维护的信息和第一题一样。

• 首先给出的[x1,y1],[x2,y2]只有两种情况，①y1<=x2,也就是两个区间中间隔了至少一个数 ②y1>x2 ，两个区间有相交

• 对于①，只有一种情况
  我们发现无论左右端点怎么选，[y1,x2]这段是必选的，所以答案就是[y1,x2]的区间和加上max(0,[x1,y1-1]的后缀答案)，再加上max(0,[x2+1,y2]的前缀答案)

对于②： 我们有4种情况

• (1) 的情况就是左右端点都在中间,所选的区间即为[x2,y1]的子区间,所以答案就是[x2,y1]的ans
• (2) 的情况就是左端点在[x1,x2],右端点在[x2,y1] ，x2这个点必取，然后加[x1,x2-1]的后缀，[x2+1,y1]的前缀
• （3）的情况和（2）对称的
• （4）左端点在[x1,x2] 右端点在[y1,y2]， 中间段的区间和必取，然后加上[x1,x2-1]的后缀，[y1+1,y2]的前缀
• 4种情况取max即可,注意区间查询前要判断l<=r

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 1e4+10;
const int mx = 40;
const ll mod = 998244353;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
struct node 
{int l,r;int sum,ans,pre,suf;node operator + (const node &f)const {node t;t.l=l,t.r=f.r;t.ans=max(suf+f.pre,max(ans,f.ans));t.sum=sum+f.sum;t.pre=max(pre,sum+f.pre);t.suf=max(f.suf,f.sum+suf);return t;}
}tree[maxn<<2];
inline void pushup(int rt) 
{tree[rt]=tree[lc]+tree[rc];
}
inline void build(int rt,int l,int r) 
{tree[rt].l=l,tree[rt].r=r;if(l == r) {scanf("%d",&tree[rt].ans);tree[rt].sum=tree[rt].pre=tree[rt].suf=tree[rt].ans;return ;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(rt);
}
inline node query(int rt,int vl,int vr) 
{int l=tree[rt].l,r=tree[rt].r;if(vl<=l && r<=vr) return tree[rt];int mid=l+r>>1;if(vr<=mid) return query(lc,vl,vr);else if(vl>mid) return query(rc,vl,vr);return query(lc,vl,vr)+query(rc,vl,vr);
}
int n;
int main()
{int t;cin>>t;while(t--) {scanf("%d",&n);build(1,1,n);int m;scanf("%d",&m);while(m--) {int x1,y1,x2,y2;scanf("%d %d %d %d",&x1,&y1,&x2,&y2);if(y1<=x2) {int ans=query(1,y1,x2).sum;//中间段必选if(x1<=y1-1)ans=max(ans,ans+query(1,x1,y1-1).suf);if(x2+1<=y2)ans=max(ans,ans+query(1,x2+1,y2).pre);printf("%d\n",ans);}else {int ans1=query(1,x2,y1).ans;//只选[x2,y1]int ans2=query(1,x2,x2).sum;if(x1<=x2-1)ans2=max(ans2,ans2+query(1,x1,x2-1).suf);if(x2+1<=y1)ans2=max(ans2,ans2+query(1,x2+1,y1).pre);int ans3=query(1,y1,y1).sum;if(x2<=y1-1)ans3=max(ans3,ans3+query(1,x2,y1-1).suf);if(y1+1<=y2)ans3=max(ans3,ans3+query(1,y1+1,y2).pre);int ans4=query(1,x2,y1).sum;if(x1<=x2-1)ans4=max(ans4,ans4+query(1,x1,x2-1).suf);if(y1+1<=y2)ans4=max(ans4,ans4+query(1,y1+1,y2).pre);printf("%d\n",max(max(ans1,ans2),max(ans3,ans4)));}}}return 0;
}

刚开始以为只是把第一题加了区间修改并且搬到树上，导致在树剖查询跳链的时候没有注意区间合并的方向性，一直wa…

• 线段树区间合并的时候，是左区间的pre和右区间的suf合并出新的ans
• 对于查询[X,Y],我们不妨把LCA->X这条链记为左链,LCA->Y记为右链,我们发现，左链对应在dfs序中是几段不相连的子段，右链同样如此，所以我们需要左右链各自跳链，独立记录答案，最后在LCA处合并答案 。
• 此外有一个要注意的是，左链在合并的时候是把深度小的顶点作为左边，深度大的作为右边 ， 然而我们查询X->Y是把深度大的作为左边，所以需要交换一下左链的pre和suf ，再进行最终的合并。
• 链的修改就是寻常的跳链。
  

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 1e5+10;
const int mx = 40;
const ll mod = 998244353;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定一棵树 查节点a到b简单路径上 点权的最大子段和(可以为空)  、 a到b路径点权改为c 
//树剖+线段树
//维护和查询过程不考虑空段情况 最后和0取max即可
//区间合并具有方向性 即左区间的后缀和右区间的前缀合并
struct 
{int to,next;
}e[maxn<<1];
int head[maxn],cnt=0;
inline void add(int v,int u)
{e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
void dfs1(int rt,int par)
{siz[rt]=1;for(int i=head[rt];i;i=e[i].next) {int to=e[i].to;if(to==par) continue;fa[to]=rt;dep[to]=dep[rt]+1;dfs1(to,rt);siz[rt]+=siz[to];if(siz[to] > siz[son[rt]]) son[rt]=to;}
}
int top[maxn],dfsc,in[maxn],pos[maxn];
void dfs2(int rt,int t) 
{top[rt]=t;in[rt]=++dfsc;pos[dfsc]=rt;if(son[rt]) dfs2(son[rt],t);for(int i=head[rt];i;i=e[i].next){int to=e[i].to;if(to==fa[rt] || to==son[rt]) continue;dfs2(to,to);}
}
int a[maxn],n;
struct node 
{#define lc rt<<1#define rc rt<<1|1int l,r;int ans,pre,suf,sum;int tag;node operator + (const node &f)const {node t;t.l=l,t.r=f.r;t.sum=sum+f.sum;t.ans=max(max(ans,f.ans),suf+f.pre);t.pre=max(pre,sum+f.pre);t.suf=max(f.suf,f.sum+suf);t.tag=maxn;//子区间已经递归下去了 此时rt的tag一定是"0"状态return t;}
}tree[maxn<<2];
inline void pushup(int rt)
{tree[rt]=tree[lc]+tree[rc];
}
inline void build(int rt,int l,int r) 
{tree[rt].l=l,tree[rt].r=r;tree[rt].tag=maxn;if(l == r) {tree[rt].pre=tree[rt].suf=tree[rt].ans=a[pos[l]];tree[rt].sum=a[pos[l]];return ;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(rt);
}
inline void change(int rt,int len,int c) 
{tree[rt].pre=tree[rt].suf=tree[rt].ans=max(c,c*len);//负数则取c  非负数取c*lentree[rt].sum=c*len;tree[rt].tag=c;
}
inline void pushdown(int rt) 
{if(tree[rt].tag != maxn) {int l=tree[rt].l,r=tree[rt].r;int mid=(l+r)>>1;change(lc,mid-l+1,tree[rt].tag);change(rc,r-mid,tree[rt].tag);tree[rt].tag=maxn;}
}
inline void upd(int rt,int vl,int vr,int c)//[vl,vr]改为c 
{int l=tree[rt].l,r=tree[rt].r;if(l>vr || r<vl) return ;if(vl<=l && r<=vr) {change(rt,r-l+1,c);return ;}int mid=l+r>>1;pushdown(rt);upd(lc,vl,vr,c);upd(rc,vl,vr,c);pushup(rt);
}
inline node query(int rt,int vl,int vr) 
{int l=tree[rt].l,r=tree[rt].r;if(vl<=l && r<=vr) return tree[rt];int mid=l+r>>1;pushdown(rt);if(vr<=mid) return query(lc,vl,vr);else if(vl>mid) return query(rc,vl,vr);return query(lc,vl,vr)+query(rc,vl,vr);
}
//x到y 对应dfs序的几段不衔接的区间
//假设x是LCA左边的  y是LCA右边的
//我们需要左右各自跳链+合并
inline node chain_q(int x,int y) 
{node ans1=(node){0,0,0,0,0,0},ans2=(node){0,0,0,0,0,0};//左边链的答案 右边链的答案int fx=top[x],fy=top[y];while(fx != fy) {if(dep[fx] < dep[fy]) { //链顶深度大的往上跳ans2=query(1,in[fy],in[y])+ans2;//加号两边的顺序不能写反y=fa[fy];fy=top[y];}else {//链顶深度大的往上跳 //ans1的方向是LCA->X  ,但是答案需要的是X->LCA,所以最后需要交换ans1的pre和suf ans1=query(1,in[fx],in[x])+ans1;//加号两边的顺序不能写反x=fa[fx];fx=top[x];}}//x在下面if(in[y] < in[x]) ans1=query(1,in[y],in[x])+ans1;//加号两边的顺序不能写反//y在下面else ans2=query(1,in[x],in[y])+ans2;//加号两边的顺序不能写反//x->LCA这条链我们算的pre suf其实是LCA->x的方向,所以需要交换一下,然后和ans2进行合并swap(ans1.pre,ans1.suf);return ans1+ans2;//加号两边的顺序不能写反
}
//链的修改是寻常跳链
inline void chain_u(int x,int y,int c) 
{int fx=top[x],fy=top[y];while(fx != fy) {if(dep[fx] < dep[fy]) swap(x,y),swap(fx,fy);upd(1,in[fx],in[x],c);x=fa[fx];fx=top[x];}//x y此时在同一条链 深度小的就是LCAif(in[x] > in[y]) swap(x,y);upd(1,in[x],in[y],c);
}
void init()
{cnt=0,dfsc=0,dep[1]=0;for(int i=1;i<=n;i++) {scanf("%d",a+i);head[i]=0;son[i]=0;}for(int i=1;i<n;i++) {int u,v;scanf("%d %d",&u,&v);add(u,v),add(v,u);}
}
int main()
{   scanf("%d",&n);init();//树剖dfs1(1,1);dfs2(1,1);//建树build(1,1,n);int m;scanf("%d",&m);while(m--) {int f,x,y,c;scanf("%d",&f);if(f==1) {scanf("%d %d",&x,&y);//可以为空段 所以和0取maxprintf("%d\n",max(0,chain_q(x,y).ans));}else {scanf("%d %d %d",&x,&y,&c);chain_u(x,y,c);}}return 0;
}

应该是最难的一题了咕咕咕