题目大意:
在一个序列上每次改动一个值,然后求出它的最大的子序列和。
思路分析:
首先我们不考虑不成环的问题。那就是直接求每一个区间的最大值就好了。
可是此处成环,那么看一下以下例子。
5
1 -2 -3 4 5
那么你会发现 max = sum - min
也就是和减去最小区间和也能够得到。
所以我们最后要得到的就是两个东西。注意题目中说的不能所有取得。所以还要推断一下 max 是不是等于 sum 的。
- #include < cstdio > #include < iostream > #include < cstring > #include < algorithm > #define maxn 100005#define lson num << 1,
- s,
- mid#define rson num << 1 | 1,
- mid + 1,
- e using namespace std;
- struct SegTree {
- int s,
- e,
- sum;
- int lmax,
- rmax;
- int lmin,
- rmin;
- int mmin,
- mmax;
- }
- ret[maxn << 2];
- void pushup(int num) {
- ret[num].sum = ret[num << 1].sum + ret[num << 1 | 1].sum;
- ret[num].lmax = max(ret[num << 1].lmax, ret[num << 1].sum + ret[num << 1 | 1].lmax);
- ret[num].lmin = min(ret[num << 1].lmin, ret[num << 1].sum + ret[num << 1 | 1].lmin);
- ret[num].rmax = max(ret[num << 1 | 1].rmax, ret[num << 1 | 1].sum + ret[num << 1].rmax);
- ret[num].rmin = min(ret[num << 1 | 1].rmin, ret[num << 1 | 1].sum + ret[num << 1].rmin);
- ret[num].mmax = max(ret[num << 1].rmax + ret[num << 1 | 1].lmax, max(ret[num << 1].mmin, ret[num << 1 | 1].mmin));
- ret[num].mmin = min(ret[num << 1].rmin + ret[num << 1 | 1].lmin, min(ret[num << 1].mmin, ret[num << 1 | 1].mmin));
- }
- void build(int num, int s, int e) {
- ret[num].s = s,
- ret[num].e = e;
- if (s == e) {
- scanf("%d", &ret[num].lmax);
- ret[num].sum = ret[num].rmax = ret[num].lmin = ret[num].rmin = ret[num].mmin = ret[num].mmax = ret[num].lmax;
- return;
- }
- int mid = (s + e) >> 1;
- build(lson);
- build(rson);
- pushup(num);
- }
- void update(int num, int s, int e, int pos, int val) {
- if (s == e) {
- ret[num].sum = ret[num].lmax = ret[num].rmax = ret[num].lmin = ret[num].rmin = ret[num].mmin = ret[num].mmax = val;
- return;
- }
- int mid = (s + e) >> 1;
- if (pos <= mid) update(lson, pos, val);
- else update(rson, pos, val);
- pushup(num);
- }
- int main() {
- int n;
- while (scanf("%d", &n) != EOF) {
- build(1, 1, n);
- int m;
- scanf("%d", &m);
- while (m--) {
- int pos,
- v;
- scanf("%d%d", &pos, &v);
- update(1, 1, n, pos, v);
- if (ret[1].mmax != ret[1].sum) printf("%d\n", max(ret[1].mmax, ret[1].sum - ret[1].mmin));
- else printf("%d\n", ret[1].sum - ret[1].mmin);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2029538.html