Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

区间和并加dp

Posted by Yt_zp at 2017-04-11 19:52:43 on Problem 2750
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 100010
#define mid ((l+r)>>1)
#define tmp (st<<1)
#define lson l,mid,tmp
#define rson mid+1,r,tmp|1
int sum[maxn<<2];///区间和
int lsum[maxn<<2];///右区间和
int rsum[maxn<<2];///左区间和
int maxx[maxn<<2];///区间最大连续子串
int lmax[maxn<<2];///左区间最大连续子串(包含左区间的开头)
int rmax[maxn<<2];///右区间最大连续子串(包含右区间的开头)
int minn[maxn<<2];///区间最小连续子串
int lmin[maxn<<2];///左区间最小连续子串(包含左区间的开头)
int rmin[maxn<<2];///右区间最小连续子串(包含右区间的开头)
int n,m;
void push_up(int st){
    sum[st]=sum[tmp]+sum[tmp|1];
    maxx[st]=max(max(maxx[tmp],maxx[tmp|1]),rmax[tmp]+lmax[tmp|1]);
    minn[st]=min(min(minn[tmp],minn[tmp|1]),rmin[tmp]+lmin[tmp|1]);
    lmax[st]=max(lmax[tmp],sum[tmp]+lmax[tmp|1]);
    rmax[st]=max(rmax[tmp|1],sum[tmp|1]+rmax[tmp]);
    lmin[st]=min(lmin[tmp],sum[tmp]+lmin[tmp|1]);
    rmin[st]=min(rmin[tmp|1],sum[tmp|1]+rmin[tmp]);
}
void build(int l,int r,int st){
    if(l==r){
        scanf("%d",&sum[st]);
        lsum[st]=rsum[st]=maxx[st]=lmax[st]=rmax[st]=minn[st]=lmin[st]=rmin[st]=sum[st];
        return ;
    }
    build(lson);
    build(rson);
    push_up(st);
}
void update(int pos,int c,int l,int r,int st){
    if(l==r){
        lsum[st]=rsum[st]=maxx[st]=lmax[st]=rmax[st]=minn[st]=lmin[st]=rmin[st]=sum[st]=c;
        return ;
    }
    if(pos<=mid)update(pos,c,lson);
    else update(pos,c,rson);
    push_up(st);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        build(1,n,1);
        scanf("%d",&m);
        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            update(x,y,1,n,1);
            if(maxx[1]==sum[1])
                printf("%d\n",sum[1]-minn[1]);
            else printf("%d\n",max(sum[1]-minn[1],maxx[1]));
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator