SP1716 GSS3 - Can you answer these queries III


这是一道比较复杂的线段树维护题目,由于最大字段和是满足区间可加性的,所以可以通过线段树来维护

void update(int id)
{
    t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
    t[id].ld=max(t[id<<1].ld,t[id<<1].sum+t[id<<1|1].ld);
    t[id].rd=max(t[id<<1|1].rd,t[id<<1|1].sum+t[id<<1].rd);
    t[id].dat=max(max(t[id<<1].dat,t[id<<1|1].dat),t[id<<1].rd+t[id<<1|1].ld);
}

建树和修改都大同小异,不过在query的时候需要去维护查询的最大字段和,所以需要传递结构体递归后往上维护

node a,b,c;
    a.sum=a.dat=a.ld=a.rd=-inf;
    b.sum=b.dat=b.ld=b.rd=-inf;
    c.sum=0;
    if(l<=mid)
    {
        a=query(id<<1,l,r);
        c.sum+=a.sum;
    }
    if(r>mid)
    {
        b=query(id<<1|1,l,r);
        c.sum+=b.sum;
    }
    c.dat=max(max(a.dat,b.dat),a.rd+b.ld);
    c.ld=max(a.ld,a.sum+b.ld);
    if(l>mid) c.ld=max(c.ld,b.ld);
    c.rd=max(b.rd,b.sum+a.rd);
    if(r<=mid) c.rd=max(c.rd,a.rd);
    return c;

更新的细节可以通过画图来理解
完整代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=50010;
const int inf=0x3f3f3f3f;
int n,m,d[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
struct node{
    int l,r,sum,dat,ld,rd;
}t[maxn*4];
void update(int id)
{
    t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
    t[id].ld=max(t[id<<1].ld,t[id<<1].sum+t[id<<1|1].ld);
    t[id].rd=max(t[id<<1|1].rd,t[id<<1|1].sum+t[id<<1].rd);
    t[id].dat=max(max(t[id<<1].dat,t[id<<1|1].dat),t[id<<1].rd+t[id<<1|1].ld);
}
void build(int id,int l,int r)
{
    t[id].l=l,t[id].r=r;
    if(l==r)
    {
        t[id].sum=t[id].dat=t[id].ld=t[id].rd=d[l];
        return;
    }
    int mid=(t[id].l+t[id].r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    update(id);
}
void change(int id,int x,int p)
{
    if(t[id].l==t[id].r)
    {
        t[id].sum=t[id].ld=t[id].rd=t[id].dat=p;
        return;
    }
    int mid=(t[id].l+t[id].r)>>1;
    if(x<=mid) change(id<<1,x,p);
    else change(id<<1|1,x,p);
    update(id);
}
node query(int id,int l,int r)
{
    if(l<=t[id].l&&r>=t[id].r) return t[id];
    int mid=(t[id].l+t[id].r)>>1;
    node a,b,c;
    a.sum=a.dat=a.ld=a.rd=-inf;
    b.sum=b.dat=b.ld=b.rd=-inf;
    c.sum=0;
    if(l<=mid)
    {
        a=query(id<<1,l,r);
        c.sum+=a.sum;
    }
    if(r>mid)
    {
        b=query(id<<1|1,l,r);
        c.sum+=b.sum;
    }
    c.dat=max(max(a.dat,b.dat),a.rd+b.ld);
    c.ld=max(a.ld,a.sum+b.ld);
    if(l>mid) c.ld=max(c.ld,b.ld);
    c.rd=max(b.rd,b.sum+a.rd);
    if(r<=mid) c.rd=max(c.rd,a.rd);
    return c;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) d[i]=read();
    build(1,1,n);
    m=read();
    for(int i=1;i<=m;i++)
    {
        int p,x,y;
        p=read(),x=read(),y=read();
        if(p) printf("%d\n",query(1,x,y).dat);
        else change(1,x,y);
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1198 JSOI2008最大数 P1198 JSOI2008最大数
这道题其实就是线段树单点修改区间查询,但开了long long scanf一定要用lld啊 调了半天,真是绝望 #include<bits/stdc++.h> using namespace std; const int maxn=
2019-07-05
下一篇 
POJ1733Parity game POJ1733Parity game
这道题给出区间奇偶性判断对错,可以维护l-1与r这样一个前缀和,假如两前缀和奇偶相同,那区间就为偶,假如奇偶不同,那区间就为奇,由于区间范围过大,可以考虑离散化,之后通过扩展域解决 #include<cstdio> #include
2019-07-05
  目录