[考试题] 山峰 摊还分析

题目大意

解题报告

这种看起来很线段树但复杂度貌似不对的题目…

首先将原数列差分, 发现一次区间加操作就变成了两个”单点加常数”和一个”区间加正数”, 若差分数列A中存在A _i <0且A _i+1 >0, 那么就出现了山峰。发现只有当某个A _i 的正负号改变时答案才会变化, 每次操作最多让两个A中元素变成负数, 那么正负变化次数是M级别的, 对每次正负变化在线段树上暴力维护即可, 均摊复杂度为O((M+N)logN), 注意若差分数组上出现0对答案也会产生影响, 也得暴力递归下去(考试时少多打了一个等号爆了70pts QAQ)。

具体实现在线段树上维护四个量lef, rig, mnv, cnt分别表示区间左端点的值, 右端点的值, 区间大于等于0的最小值, 和该区间山峰数量。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
const int MAXN = 100010;
const LL  LLINF = 0x3f3f3f3f3f3f3f3fLL;
namespace IBT {
    const int MAXD = MAXN*5;
    int cnt[MAXD];
    LL mnv[MAXD], lef[MAXD], rig[MAXD], lz[MAXD];
    inline void updata (int u) {
        cnt[u] = cnt[u<<1]+cnt[(u<<1)+1];
        lef[u] = lef[u<<1], rig[u] = rig[(u<<1)+1];
        cnt[u] += (rig[u<<1] < 0 && lef[(u<<1)+1] > 0);
        mnv[u] = min(mnv[u<<1], mnv[(u<<1)+1]);
    }
    int * src;
    inline void build (int u, int l, int r) {
        if(l == r) {
            if(src[l] >= 0) mnv[u] = src[l];
            else mnv[u] = LLINF;
            lef[u] = rig[u] = src[l];
            return ;
        }
        int mid = (l+r)>>1;
        build(u<<1, l, mid);
        build((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline void add (int u, LL val) {
        mnv[u] += val;
        lef[u] += val;
        rig[u] += val;
        lz[u] += val;
    }
    inline void pushdown (int u) {
        if(lz[u]) {
            add(u<<1, lz[u]);
            add((u<<1)+1, lz[u]);
            lz[u] = 0;
        }
    }
    int agl, agr; LL agv;
    inline void addInterval (int u, int l, int r) {
        if(agr < l || r < agl) return ;
        if(agl <= l && r <= agr) {
            if(mnv[u]+agv >= 0 || l == r) { // agv < 0 没有新的山峰或者到头
                add(u, agv);
                if(mnv[u] < 0) mnv[u] = LLINF;
                return ;
            }
        }
        pushdown(u);
        int mid = (l+r)>>1;
        addInterval(u<<1, l, mid);
        addInterval((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline void singleAdd (int u, int l, int r) {
        if(agr < l || r < agl) return ;
        if(l == r) {
            add(u, agv);
            if(lef[u] >= 0) mnv[u] = lef[u];
            else mnv[u] = LLINF;
            return ;
        }
        pushdown(u);
        int mid = (l+r)>>1;
        singleAdd(u<<1, l, mid);
        singleAdd((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline int answer () {return cnt[1];}
}
int A[MAXN], delt[MAXN];
int main () {
    int N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++)
        A[i] = getInt();
    for(int i = 2; i<=N; i++)
        delt[i] = A[i-1]-A[i];
    IBT::src = delt;
    IBT::build(1, 2, N);
    printf("%d\n", IBT::answer());
    for(int i = 1; i<=M; i++) {
        int l = getInt(), r = getInt(), a = getInt(), d = getInt();
        if(l != 1) {IBT::agl = l, IBT::agr = l, IBT::agv = -a; IBT::singleAdd(1, 2, N);}
        if(l < r) {IBT::agl = l+1, IBT::agr = r, IBT::agv = -d; IBT::addInterval(1, 2, N);}
        if(r != N) {IBT::agl = r+1, IBT::agr = r+1; IBT::agv = (LL)a+(LL)(r-l)*d; IBT::singleAdd(1, 2, N);}
        printf("%d\n", IBT::answer());
    }
}