P4513 题解

这还是我第一次给紫题写题解。。。

---

题目大意：

给定$n$个公园的美观值（可能有负数），求出美观值和最大的连续花园区间 $[l,r]$

实际上就是求区间最大子段和。。。

---

思路：

这是一道典型的区间统计问题，对于区间统计问题，我们一般使用线段树解决

线段树教程

为了求出区间最大子段和，对于每个区间x，我们需要计算以下四个值：

sum[x] : x所代表区间的区间和
ldat[x] : 紧靠区间左端的最大子段和
rdat[x] : 紧靠区间右端的最大子段和
dat[x] : 区间最大子段和

这些值如何求出呢？

首先，我们考虑$dat$:

对于一个区间的$dat$，它只能由三个途径得来:

1. 完全在左子区间，即左子区间的$dat$(绿色部分)
2. 完全在右子区间，即右子区间的$dat$(红色部分)
3. 跨越中点，即左子区间的$rsum$加上右子区间的$lsum$(黄色部分)

那么，如何求出$ldat$和$rdat$呢？

由于$ldat$和$rdat$的求法相似，只是方向不同，这里只考虑$ldat$的求法 $\dots$

$ldat$更加简单，只有两种情况：

1. 完全在左子区间，即左子区间的$ldat$(绿色部分)
2. 跨越中点，即左子区间的$sum +$ 右子区间的 $ldat$(红色部分)

看到这里，相信大家都已经知道$rdat$怎么求了，这里就不在赘述。。。

至此，问题得到完美解决 $\dots$

怎么可能

---

Tips：

1. 测试数据可能会出现$a>b$的情况，需要进行交换…(血的教训)
2. 查询时要同时返回4个数据并按要求归并…

---

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500001;
int n,m;
struct segment_tree{
  int l,r;
  int sum,lsum,rsum,dat;
};
segment_tree tree[maxn*4];
//宏定义
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define lsum(x) tree[x].lsum
#define rsum(x) tree[x].rsum
#define dat(x) tree[x].dat
int read()//快读
{
  int s=0,w=1;
  char c=getchar();
  while(c<'0' || c>'9')
  {
    if(c=='-') w=-1;
    c=getchar();
  }
  while(c>='0' && c<='9')
  {
    s=(s<<3)+(s<<1)+(c^48);
    c=getchar();
  }
  return s*w;
}
void update(int p)//归并信息
{
  sum(p)=sum(p<<1)+sum(p<<1|1); //区间和
  lsum(p)=max(lsum(p<<1),sum(p<<1)+lsum(p<<1|1)); //紧靠区间左端的最大子段和
  rsum(p)=max(rsum(p<<1|1),sum(p<<1|1)+rsum(p<<1));//紧靠区间右端的最大子段和
  dat(p)=max({dat(p<<1),dat(p<<1|1),rsum(p<<1)+lsum(p<<1|1)}); //区间最大子段和
}
void build(int p,int l,int r) //建树
{
  l(p)=l,r(p)=r;
  if(l(p)==r(p)){ //如果是叶子结点
    sum(p)=lsum(p)=rsum(p)=dat(p)=read(); //初始化的同时读入，高效建树
    return;
  }
  int mid=(l+r)>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
  update(p);
}
void change(int p,int addr,int c) //单点修改
{
  if(l(p)==r(p))
  {
    sum(p)=lsum(p)=rsum(p)=dat(p)=c;
    return;
  }
  int mid=(l(p)+r(p))>>1;
  if(addr<=mid) change(p<<1,addr,c);
  else if(addr>mid) change(p<<1|1,addr,c);
  update(p);
}
segment_tree ask(int p,int l,int r) //区间查询（要同时返回4个数据）
{
  if(l<=l(p) && r>=r(p)) return tree[p];
  int ans=0xc0c0c0c0;
  int mid=(l(p)+r(p))>>1;
  if(r<=mid) return ask(p<<1,l,r);
  if(l>mid) return ask(p<<1|1,l,r);
  else{
    segment_tree x,y,ans;
    x=ask(p<<1,l,r),y=ask(p<<1|1,l,r);
    ans.sum=x.sum+y.sum;
    ans.lsum=max(x.lsum,x.sum+y.lsum);
    ans.rsum=max(y.rsum,y.sum+x.rsum);
    ans.dat=max({x.dat,y.dat,x.rsum+y.lsum});
    return ans;
  }
//  return ans;
}
int k,a,b;
int main()
{
  n=read(),m=read();
  build(1,1,n);
  for(int i=1;i<=m;i++)
  {
    k=read();
    if(k==1)
    {
      a=read(),b=read();
      if(a>b) swap(a,b);
      printf("%d\n",ask(1,a,b).dat);
    }
    else if(k==2)
    {
      a=read(),b=read();
      change(1,a,b);
    }
  }
  return 0;
}