首页 > 其他 > 详细

SP1716 GSS3 - Can you answer these queries III(单点修改,区间最大子段和)

时间:2018-07-20 20:48:12      阅读:175      评论:0      收藏:0      [点我收藏+]

题意翻译

nnn 个数, qqq 次操作

操作0 x yAxA_xAx? 修改为 yyy

操作1 l r询问区间 [l,r][l, r][l,r] 的最大子段和

题目描述

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输入输出格式

输入格式:

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输出格式:

For each query, print an integer as the problem required.

思路:

这道题与GSS1很像(没做过GSS1的点这里

但这个题怎么办呢?

大家应该记得,我做GSS1时,并没有建树这个步骤

而是直接将原始节点都变为-inf,然后通过单点修改的方式建树

那么GSS3就很简单了

我们不需要动修改函数(因为都是单点)

直接在循环中引用即可(我才不会告诉你我是先写的GSS3

代码:

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rii register int i
#define rij register int j
#define inf 1073741824
#define rs 65536
using namespace std;
struct nod{
    int lm,rm,maxn,sum;
}x[6000005];
int n,q,cz,x1,y1;
void add(int wz,int l,int r,int val,int bh)
{
    if(l==r&&l==wz)
    {
        x[bh].maxn=val;
        x[bh].lm=val;
        x[bh].rm=val;
        x[bh].sum=val;
        return;
    }
    int ltt=(l+r)/2;
    if(wz<=ltt)
    {
        add(wz,l,ltt,val,bh*2);
    }
    else
    {
        add(wz,ltt+1,r,val,bh*2+1);
    }
    x[bh].sum=x[bh*2].sum+x[bh*2+1].sum;
    x[bh].lm=max(x[bh*2].lm,x[bh*2].sum+x[bh*2+1].lm);
    x[bh].rm=max(x[bh*2+1].rm,x[bh*2+1].sum+x[bh*2].rm);
    x[bh].maxn=max(x[bh*2].maxn,max(x[bh*2+1].maxn,x[bh*2].rm+x[bh*2+1].lm));
}
nod query(int l,int r,int nl,int nr,int bh)
{
    nod an,bn;
    if(l<nl)
    {
        l=nl;
    }
    if(r>nr)
    {
        r=nr;
    }
    if(nl==l&&nr==r)
    {
        an=x[bh];
        return an;
    }
    int ltt=(nl+nr)/2;
    if(l<=ltt&&r<=ltt)
    {
        return an=query(l,r,nl,ltt,bh*2);
    }
    if(r>ltt&&l>ltt)
    {
        return bn=query(l,r,ltt+1,nr,bh*2+1);
    }
    else
    {
        an=query(l,r,nl,ltt,bh*2);
        bn=query(l,r,ltt+1,nr,bh*2+1);
        an.maxn=max(an.maxn,max(bn.maxn,an.rm+bn.lm));
        an.lm=max(an.lm,an.sum+bn.lm);
        an.rm=max(bn.rm,bn.sum+an.rm);
        an.sum=an.sum+bn.sum;
        return an;
    }
    
}
int main()
{
//    freopen("brs.in","r",stdin);
//    freopen("brs.out","w",stdout);
    for(rii=1;i<=150005;i++)
    {
        x[i].lm=-inf;
        x[i].rm=-inf;
        x[i].maxn=-inf;
    }
    scanf("%d",&n);
    for(rii=1;i<=n;i++)
    {
        int ltt;
        scanf("%d",&ltt);
        add(i,1,rs,ltt,1);
    }
    scanf("%d",&q);
    for(rii=1;i<=q;i++)
    {
        scanf("%d%d%d",&cz,&x1,&y1);
        if(cz==1)
        {
            nod ans=query(x1,y1,1,rs,1);
            printf("%d\n",ans.maxn);
        }
        else
        {
            add(x1,1,rs,y1,1);
        }
    }
}

 

SP1716 GSS3 - Can you answer these queries III(单点修改,区间最大子段和)

原文:https://www.cnblogs.com/ztz11/p/9343435.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!