快递网站设计公司,做门户网站公司,加盟全屋定制,东莞制作网站题目#xff1a;Potted Flower 大意#xff1a;该你一个换环#xff0c;求环上的最大连续的和#xff08;如果最大和包含所有数#xff0c;要求减去最小的一个#xff09;。 思路#xff1a;这道题的思路并不难#xff0c;需要在线段树里维护区间的最大和#xff0c… 题目Potted Flower 大意该你一个换环求环上的最大连续的和如果最大和包含所有数要求减去最小的一个。 思路这道题的思路并不难需要在线段树里维护区间的最大和最小和应为是环状的所以答案有可能是总和减去最小和然后需要用一个区间左边的最大最小右边的最大最小来维护区间的最大和最小和。这道题的解法就是这样。 代码奉上 #includecstdio
#includealgorithm
using namespace std;
#define M(i) ((t[(i)].l t[i].r) 1)
const int MAXN 1e5 5;
const int INF 1e9;
struct node
{int l,r,lmx,rmx,lmn,rmn,sum,mx,mn;
}t[MAXN 2];
int n, p[MAXN], m;
void build(int i, int l, int r)
{t[i].l l;t[i].r r;t[i].lmx t[i].rmx t[i].mx -INF;t[i].lmn t[i].rmn t[i].mn INF;if(l r) {p[l] i; return;}build(i1, l, M(i));build(i1|1, M(i)1, r);
}
int max(int a,int b,int c)
{return max(a,max(b,c));
}
int min(int a,int b,int c)
{return min(a,min(b,c));
}
void upd(int pos, int v)
{int i p[pos];t[i].lmx t[i].rmx t[i].sum t[i].lmn t[i].rmn t[i].mx t[i].mn v;i 1;while(i){t[i].lmx max(t[i1].lmx, t[i1].sum t[i1|1].lmx);t[i].lmn min(t[i1].lmn, t[i1].sum t[i1|1].lmn);t[i].rmx max(t[i1|1].rmx, t[i1|1].sum t[i1].rmx);t[i].rmn min(t[i1|1].rmn, t[i1|1].sum t[i1].rmn);t[i].sum t[i1].sum t[i1|1].sum;t[i].mx max(t[i1].mx,t[i1].rmxt[i1|1].lmx,t[i1|1].mx);t[i].mn min(t[i1].mn,t[i1].rmnt[i1|1].lmn,t[i1|1].mn);i 1;}
}
int main()
{int t1, t2;scanf(%d, n);build(1, 1, n);for(int i 1; i n; i){scanf(%d, t1);upd(i, t1);}scanf(%d, m);for(int i 1; i m; i){scanf(%d%d, t1, t2);upd(t1, t2);if(t[1].mx t[1].sum t[1].sum 0)printf(%d\n,t[1].sum - t[1].mn);elseprintf(%d\n,max(t[1].mx,t[1].sum - t[1].mn));}return 0;
}转载于:https://www.cnblogs.com/geng4512/p/5296950.html
