poj 2750 Potted Flower(线段树区间合并)

2024-08-28 10:18

本文主要是介绍poj 2750 Potted Flower(线段树区间合并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://poj.org/problem?id=2750


有n个数围成一个圈,每次可以将a位置上的数变为b,对每个操作,输出区间的最大连续子段和,连续的子段长度不能超过n。


区间合并问题,因为是求连续子段的和。先把圈从1和n之间断开,变为一条链,先在链上求最长连续的和。这个最长连续的和取左节点最长连续和,右节点最长连续和,左节点从右边数最大连续和加上右节点从左边数最大连续和三者的最大值。

特殊情况就是当区间全为正的时候,最长连续和等于1~n的和,这违背题意,它应该等于区间总和减去区间内最小连续的和。因此节点内在记录最大连续和的同时还要记录最小连续和。剩下的就是push_up和单点更新了。


#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define PP pair<LL,LL>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
const int mod = 1000000007;struct node
{int l,r;int lmin,rmin;//分别从左右两边数最小连续的和int lmax,rmax;//分别从左右两边数最大连续的和int sum,smax,smin;//区间总和,最大连续和,最小连续和
}tree[maxn*4];int a[maxn];void push_up(int v)
{tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;tree[v].lmax = max(tree[v*2].lmax, tree[v*2].sum + tree[v*2+1].lmax);tree[v].lmin = min(tree[v*2].lmin, tree[v*2].sum + tree[v*2+1].lmin);tree[v].rmax = max(tree[v*2+1].rmax, tree[v*2+1].sum + tree[v*2].rmax);tree[v].rmin = min(tree[v*2+1].rmin, tree[v*2+1].sum + tree[v*2].rmin);tree[v].smax = max(max(tree[v*2].smax,tree[v*2+1].smax),tree[v*2].rmax+tree[v*2+1].lmax);tree[v].smin = min(min(tree[v*2].smin,tree[v*2+1].smin),tree[v*2].rmin+tree[v*2+1].lmin);
}void build(int v, int l, int r)
{tree[v].l = l;tree[v].r = r;if(l == r){tree[v].lmax = tree[v].lmin = tree[v].rmax = tree[v].rmin = a[l];tree[v].smax = tree[v].smin = tree[v].sum = a[l];return;}int mid = (l+r) >> 1;build(v*2,l,mid);build(v*2+1,mid+1,r);push_up(v);
}void update(int v, int pos, int val)
{if(tree[v].l == tree[v].r){tree[v].lmax = tree[v].lmin = tree[v].rmax = tree[v].rmin = val;tree[v].smax = tree[v].smin = tree[v].sum = val;return;}int mid = (tree[v].l + tree[v].r) >> 1;if(pos <= mid)update(v*2,pos,val);else update(v*2+1,pos,val);push_up(v);
}int main()
{int n,m;int x,y;while(~scanf("%d",&n)){for(int i = 1; i <= n; i++)scanf("%d",&a[i]);scanf("%d",&m);build(1,1,n);for(int i = 1; i <= m; i++){scanf("%d %d",&x,&y);update(1,x,y);if(tree[1].smax == tree[1].sum && tree[1].sum > 0)printf("%d\n",tree[1].sum - tree[1].smin);else{printf("%d\n",max(tree[1].smax,tree[1].sum - tree[1].smin));}}}return 0;
}


这篇关于poj 2750 Potted Flower(线段树区间合并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1114477

相关文章

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO