首页 > 代码库 > POJ 2570 线段树
POJ 2570 线段树
Potted Flower
Time Limit: 2000 MS Memory Limit: 65536 KB
64-bit integer IO format: %I64d , %I64u Java class name: Main
[Submit] [Status] [Discuss]
Description
The little cat takes over the management of a new park. There is a large circular statue in the center of the park, surrounded by N pots of flowers. Each potted flower will be assigned to an integer number (possibly negative) denoting how attractive it is. See the following graph as an example:
(Positions of potted flowers are assigned to index numbers in the range of 1 ... N. The i-th pot and the (i + 1)-th pot are consecutive for any given i (1 <= i < N), and 1st pot is next to N-th pot in addition.)
The board chairman informed the little cat to construct "ONE arc-style cane-chair" for tourists having a rest, and the sum of attractive values of the flowers beside the cane-chair should be as large as possible. You should notice that a cane-chair cannot be a total circle, so the number of flowers beside the cane-chair may be 1, 2, ..., N - 1, but cannot be N. In the above example, if we construct a cane-chair in the position of that red-dashed-arc, we will have the sum of 3+(-2)+1+2=4, which is the largest among all possible constructions.
Unluckily, some booted cats always make trouble for the little cat, by changing some potted flowers to others. The intelligence agency of little cat has caught up all the M instruments of booted cats‘ action. Each instrument is in the form of "A B", which means changing the A-th potted flowered with a new one whose attractive value equals to B. You have to report the new "maximal sum" after each instruction.
(Positions of potted flowers are assigned to index numbers in the range of 1 ... N. The i-th pot and the (i + 1)-th pot are consecutive for any given i (1 <= i < N), and 1st pot is next to N-th pot in addition.)
The board chairman informed the little cat to construct "ONE arc-style cane-chair" for tourists having a rest, and the sum of attractive values of the flowers beside the cane-chair should be as large as possible. You should notice that a cane-chair cannot be a total circle, so the number of flowers beside the cane-chair may be 1, 2, ..., N - 1, but cannot be N. In the above example, if we construct a cane-chair in the position of that red-dashed-arc, we will have the sum of 3+(-2)+1+2=4, which is the largest among all possible constructions.
Unluckily, some booted cats always make trouble for the little cat, by changing some potted flowers to others. The intelligence agency of little cat has caught up all the M instruments of booted cats‘ action. Each instrument is in the form of "A B", which means changing the A-th potted flowered with a new one whose attractive value equals to B. You have to report the new "maximal sum" after each instruction.
Input
There will be a single test data in the input. You are given an integer N (4 <= N <= 100000) in the first input line.
The second line contains N integers, which are the initial attractive value of each potted flower. The i-th number is for the potted flower on the i-th position.
A single integer M (4 <= M <= 100000) in the third input line, and the following M lines each contains an instruction "A B" in the form described above.
Restriction: All the attractive values are within [-1000, 1000]. We guarantee the maximal sum will be always a positive integer.
The second line contains N integers, which are the initial attractive value of each potted flower. The i-th number is for the potted flower on the i-th position.
A single integer M (4 <= M <= 100000) in the third input line, and the following M lines each contains an instruction "A B" in the form described above.
Restriction: All the attractive values are within [-1000, 1000]. We guarantee the maximal sum will be always a positive integer.
Output
For each instruction, output a single line with the maximum sum of attractive values for the optimum cane-chair.
Sample Input
53 -2 1 2 -542 -25 -52 -45 -1
Sample Output
4435
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define ls rt<<1#define rs rt<<1|1#define MAX(x,y) ((x)>(y)?(x):(y))#define MIN(x,y) ((x)>(y)?(y):(x))#define MAXN 100010int N,M;int a[MAXN];struct seg_tree{ int l,r; int lmax,rmax,summax; int lmin,rmin,summin; int sum;}tree[MAXN*3];void PushUp(int rt){ tree[rt].sum=tree[ls].sum+tree[rs].sum; tree[rt].lmax=MAX(tree[ls].lmax,tree[ls].sum+tree[rs].lmax); tree[rt].rmax=MAX(tree[rs].rmax,tree[rs].sum+tree[ls].rmax); tree[rt].summax=MAX(MAX(tree[ls].summax,tree[rs].summax),tree[ls].rmax+tree[rs].lmax); tree[rt].lmin=MIN(tree[ls].lmin,tree[ls].sum+tree[rs].lmin); tree[rt].rmin=MIN(tree[rs].rmin,tree[rs].sum+tree[ls].rmin); tree[rt].summin=MIN(MIN(tree[ls].summin,tree[rs].summin),tree[ls].rmin+tree[rs].lmin);}void build(int rt,int l,int r){ if(l>r) return; tree[rt].l=l; tree[rt].r=r; int mid=(l+r)/2; if(l==r) { tree[rt].sum=a[l]; tree[rt].lmax=tree[rt].rmax=tree[rt].summax=a[l]; tree[rt].lmin=tree[rt].rmin=tree[rt].summin=a[l]; return; } build(rt*2,l,mid); build(rt*2+1,mid+1,r); PushUp(rt);}void update(int rt,int pos,int val){ if(tree[rt].l==tree[rt].r && tree[rt].l==pos) { tree[rt].sum=val; tree[rt].lmax=tree[rt].rmax=tree[rt].summax=val; tree[rt].lmin=tree[rt].rmin=tree[rt].summin=val; return; } int m=(tree[rt].l + tree[rt].r)>>1; if(pos<=m) update(rt*2,pos,val); else update(rt*2+1,pos,val); PushUp(rt);}int main(){ while(scanf("%d",&N)!=EOF) { for(int i=1;i<=N;i++) scanf("%d",&a[i]); build(1,1,N); scanf("%d",&M); int pos,val; while(M--) { scanf("%d%d",&pos,&val); update(1,pos,val); if(tree[1].sum==tree[1].summax) printf("%d\n",tree[1].sum-tree[1].summin); else printf("%d\n",MAX(tree[1].summax,tree[1].sum-tree[1].summin)); } } return 0;}
题意：给定一个环形序列，进行在线操作，每次修改一个元素，输出环上的最大连续子列的和，但不能是完全序列。
分析:
如果不是环的话，只是一个序列，用线段树很方便求，所以将环从某一点切开成一个序列。
那么答案的最大连续和可能包含断点（换种想法，包含断点时的最大连续和即为 sum-区间最小的连续和）
1，若是所有的数都大于0，那么最大连续和（必须断开一个）即为 总和sum-最小非空连续和。
2，若是区间最小连续和小于0，那么答案就是MAX(区间最大连续和，sum-最小非空连续和)。即分为包含断点和不包含的比较。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。