C++ – Three Sequences 思维 差分

原题链接

https://codeforces.com/contest/1406/problem/D

思路

样例中a=2,-1,7,3;

差分为-3,8,-4;

设(b[1]=x)+(c[1]=y)=a[1];

∵b[1]=c[2]>=…>=c[n]

x+(y-3)=(x-1)+(y-2)=(x+1)+(y-4)=…=a[2]

∴b[2]=x c[2]=y-3为最优解

其他的解都会导致b[n]或者c[1]变大 使最后答案不是最小

即:差分>0时,将差分的值加入到b数组中;差分

第1个元素不加入sum!!!

设正差分的和为sum，则b[n]=x+sum y=c[1]=a[1]-x

ans=max(b[n],c[1])=max(x+sum,a[1]-x)

由函数y=x+sum与y=-x+a[1]的图像可得

当x=(a[1]-sum)/2时，ans取最小值 所以统计正差分的和sum和a[1]即可

对于修改操作，区间[l,r]中每个数都加x

所以内部差分不变，只需要更改l与r+1的差分

具体步骤：

1.若原差分l(或者r+1)>0，改变差分前需要从sum中减出来差分l(或者r+1)

sum改变前提：l!=1 r+1

2.改变差分:差分[l]+=x; 差分[r+1]-=x;

3.若改变后差分l(或者r+1)>0，改变后sum+=差分l(或者r+1)

sum改变前提：l!=1 r+1

4.若l==1，a[1]+=x; 5.与修改操作前同理，计算ans输出就行

#include<iostream>
#include<cstring>
#include<algorithm>
#define go(a,b,c) for(ll a=b;a<=c;a++)
using namespace std;
typedef long long ll;
ll n, a[100010], q, l, r, x, cha[100010], tot;
int main() {
    cin >> n;
    go(i, 1, n) {
        cin >> a[i];
        cha[i] = a[i] - a[i - 1];
        if (cha[i] > 0 && i != 1)
            tot += cha[i];
    }
    ll xx = (a[1] - tot) / 2;
    cout << max(xx + tot, a[1] - xx) << endl;
    cin >> q;
    while (q--) {
        cin >> l >> r >> x;
        if (l == 1)
            a[1] += x;
        else {
            tot -= cha[l] > 0 ? cha[l] : 0;
            cha[l] += x;
            tot += cha[l] > 0 ? cha[l] : 0;
        }
        if (r + 1 <= n) {
            tot -= cha[r + 1] > 0 ? cha[r + 1] : 0;
            cha[r + 1] -= x;
            tot += cha[r + 1] > 0 ? cha[r + 1] : 0;
        }
        xx = (a[1] - tot) / 2;
        cout << max(xx + tot, a[1] - xx) << endl;
    }
    return 0;
}