题解 CF1406D 【Three Sequences】

tommymio · 2020-09-22 17:28:42 · 题解

非常好的一道性质题。

手玩+稍加证明就可以发现，a_i 增时，只会影响 b_i，a_i 降时只会影响 c_i。

由于 b_i 不降，c_i 不增，所以 b,c 两序列的最大值分别为 b_n,c_1，而又有 b_n=b_1+\sum_{i=2}^nb_i-b_{i-1}，和 \max \{b_n,c_1\}=\left\lceil\frac{b_n+c_1}{2}\right\rceil，于是有 \left\lceil\frac{b_n+c_1}{2}\right\rceil=\left\lceil\frac{(b_1+c_1)+\sum_{i=2}^nb_i-b_{i-1}}{2}\right\rceil。

发现 b_1+c_1 就是 a_1，那么我们必须要求出 \sum_{i=2}^n b_i-b_{i-1}，不妨记 b_i-b_{i-1} 为 \Delta_i，则该式可以记作 \sum_{i=2}^n \Delta_i 那么根据上述性质，\Delta_i 与 a_i 的关系式是 \Delta_i=(a_i-a_{i-1})\times[a_i\geq a_{i-1}]，这个东西可以预处理出来。

加上修改操作又该怎么做呢？我们发现一次修改事实上只会影响 d_l,d_{r+1} 的值，直接修改 d_l,d_{r+1}，并且用 \text{BIT} 维护 a_i 的区间增量即可。

#include<cstdio>
#include<cmath>
typedef long long ll;
int n,a[100005];;
ll sum[100005],d[100005];
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline void add(int x,int val) {for(;x<=n;x+=x&(-x)) sum[x]+=val;}
inline ll ask(int x) {ll res=0; for(;x;x-=x&(-x)) res+=sum[x]; return res;}
int main() {
    n=read(); ll cur=0;
    for(register int i=1;i<=n;++i) a[i]=read();
    for(register int i=2;i<=n;++i) d[i]=(a[i]-a[i-1])*(a[i]>=a[i-1]);
    for(register int i=2;i<=n;++i) cur+=d[i];
    printf("%lld\n",(ll)ceil((a[1]+cur)*1.00/2));
    int T=read();
    while(T--) {
        int l=read(),r=read(),x=read();
        add(l,x);if(r<n) add(r+1,-x);
        ll a1=a[l-1]+ask(l-1),a2=a[l]+ask(l);
        if(l>1) {cur-=d[l];d[l]=(a2-a1)*(a2>=a1);cur+=d[l];}
        a1=a[r]+ask(r),a2=a[r+1]+ask(r+1);
        if(r<n) {cur-=d[r+1];d[r+1]=(a2-a1)*(a2>=a1);cur+=d[r+1];}
        printf("%lld\n",(ll)ceil((a[1]+ask(1)+cur)*1.00/2));    
    }
    return 0;
}