首页 > 代码库 > POJ 2750 Potted Flower (线段树区间合并)
POJ 2750 Potted Flower (线段树区间合并)
开始懵逼找不到解法，看了网上大牛们的题解才发现是区间合并。。。
给你n个数形成一个数列环，然后每次进行一个点的修改，并输出这个数列的最大区间和（注意是环，并且区间最大只有n-1个数）
其实只需要维护：最大区间的值 mmax，最小区间的值 mmin。当然要维护这两个值就需要维护：左端点开始的最大与最小区间的值，右端点开始的最大与最小区间的值。然后是数列的总和，数列的最大值，最小值。然后就是查询时的区间最大值等于整个区间的mmax和区间和sum减去mmin，但是当都是非负数，都是负数时要特判。亏我刷了那么多线段树还是没有看出来，果然还是自己太弱
#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstring>#include<stdlib.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0#define mul(a,b) (a<<b)#define dir(a,b) (a>>b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<30;const double Pi=acos(-1.0);const int Max=100010<<2;struct node{ int mmax,lmax,rmax,mmin,lmin,rmin; int sum,manx,minx; void init(int num) { mmax=lmax=rmax=mmin=lmin=rmin=manx=minx=sum=num; }} segtr[Max];int non;//非负数个数int nmin(int a,int b){ return a>b?b:a;}int nmax(int a,int b){ return a>b?a:b;}void Upnow(int now,int next)//关键{ segtr[now].minx=nmin(segtr[next].minx,segtr[next|1].minx);//区间最值需要运用线段树 segtr[now].manx=nmax(segtr[next].manx,segtr[next|1].manx); segtr[now].sum=segtr[next].sum+segtr[next|1].sum; segtr[now].lmax=nmax(segtr[next].lmax,segtr[next].sum+segtr[next|1].lmax);//左端点开始的区间最大值可能跨左右区间 segtr[now].rmax=nmax(segtr[next|1].rmax,segtr[next|1].sum+segtr[next].rmax); segtr[now].mmax=nmax(nmax(segtr[next].mmax,segtr[next|1].mmax),segtr[next].rmax+segtr[next|1].lmax);//区间最大值也可能是跨左右区间的最大值 segtr[now].lmin=nmin(segtr[next].lmin,segtr[next].sum+segtr[next|1].lmin); segtr[now].rmin=nmin(segtr[next|1].rmin,segtr[next|1].sum+segtr[next].rmin); segtr[now].mmin=nmin(nmin(segtr[next].mmin,segtr[next|1].mmin),segtr[next].rmin+segtr[next|1].lmin); return;}void Create(int sta,int enn,int now){ if(sta==enn) { scanf("%d",&segtr[now].sum); if(segtr[now].sum>=0) non++; segtr[now].init(segtr[now].sum); return; } int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next); Create(mid+1,enn,next|1); Upnow(now,next); return;}void Update(int sta,int enn,int now,int x,int y){ if(sta==enn&&sta==x) { if(segtr[now].sum>=0&&y<0) non--; if(segtr[now].sum<0&&y>=0) non++; segtr[now].init(y); return; } int mid=dir(sta+enn,1); int next=mul(now,1); if(mid>=x) Update(sta,mid,next,x,y); else Update(mid+1,enn,next|1,x,y); Upnow(now,next); return;}int main(){ int n,m; int pos,val; while(~scanf("%d",&n)) { non=0; Create(1,n,1); scanf("%d",&m); for(int i=0; i<m; i++) { scanf("%d %d",&pos,&val); Update(1,n,1,pos,val); if(non==n)//全为非负数 printf("%d\n",segtr[1].sum-segtr[1].minx); else if(non==0) printf("%d\n",segtr[1].manx); else printf("%d\n",nmax(segtr[1].mmax,segtr[1].sum-segtr[1].mmin));//环的处理可以用和减去区间最小值 } } return 0;}
POJ 2750 Potted Flower (线段树区间合并)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。