题目大意
解题报告
这种看起来很线段树但复杂度貌似不对的题目…
首先将原数列差分, 发现一次区间加操作就变成了两个”单点加常数”和一个”区间加正数”, 若差分数列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()); } }
Join the discussion