「Ynoi2015」纵使日薄西山

发表于 | 更新于 | 分类于 | 阅读次数：

感觉失去卡常的兴致了……，虽然这个题明明不卡常。

Idea：ccz Solution：ccz Std：ccz Data：ccz

对这题的评价：3/11

[Luogu 5069]

题意简述

维护一个长度为 $n$ 的正整数序列 $a$ ， $m$ 次修改序列中某个位置的值。

每次修改后问对序列重复进行以下操作，需要进行几次操作才能使序列变为全 $0$ （询问后序列和询问前相同，不会变为全 $0$ ）：

选出序列中最大值的出现位置，若有多个最大值则选位置标号最小的一个，设位置为 $x$ ，则将 $a{x-1},a_x,a_{x+1}$ 的值减 $1$ ，如果序列中存在小于 $0$ 的数，则把对应的数改为 $0$ 。

$1\le n, m\le 10^5, 1\le a_i \le 10^9$ 。

主要思路

如果一个位置 $x$ 是极大值（即 $a_{x-1} < a_x, a_x \ge a_{x + 1}$ ），显然位置 $x - 1$ 和位置 $x + 1$ 不会成为最大值，且位置 $x$ 会成为最大值 $a_x$ 次。而操作过位置 $x$ 后，可能会出现新的极大值。

分析找极大值的过程，发现是从初始每个极大值开始向两侧隔一个位置取一个位置，直到到达极小值或边界为止。一个极小值仅当到两侧第一个极大值的距离均为偶数时才成为极大值。

所以对奇数位置和偶数位置分别开一棵树状数组维护一下，然后用一棵平衡树记录序列的极大值和极小值位置。这样就能够快速计算两个极值之间的区间的贡献。

对于单点修改，只会影响两侧最多分别两个区间，重新计算贡献即可。

时间复杂度 $O(n\log_2{n})$ 。

参考代码

写得好的话细节其实不多。

开始想要把两个极值之间的答案记在前一个极值上，然后发现很难写……

于是把极大值到两侧极小值这两段区间的答案记在极大值上，极小值上只记录自己有没有贡献。

然后由于要访问前两个和后两个极值，所以开始先插入一些初值即可减少讨论。

总之想好了再码还是比较容易的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        reg int ans=0,f=1; reg char c=getchar();
        while(!isdigit(c)) f^=(c=='-'), c=getchar();
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48);
        return f?ans:-ans;
    }
    Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
    Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
    #define using_mod
    const int mod = 998244353, N = 100010;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

typedef set<int>::iterator iter;
set<int> s;

int n, m, a[N];
LL ans;

struct BIT{//树状数组
    LL a[N];
    inline void update(int x, LL v){ if(x) for(; x <= n; x += x & (-x)) a[x] += v; }
    inline LL query(int x){
        if(x <= 0) return 0;
        if(x > n) x = n;
        reg LL res = 0;
        for(; x; x -= x & (-x)) res += a[x];
        return res;
    }
    inline LL query(int l, int r){ return l <= r ? query(r) - query(l - 1) : 0; }
}BT[2];

inline LL get_num(iter it){//求贡献直接传迭代器进来
    Rint x = *it;
    if(x <= 0 || x > n) return 0;
    Rint opt = a[x - 1] < a[x] && a[x] >= a[x + 1];
    reg iter nxt = it, pre = it;
    ++nxt, --pre;
    if(opt){
        return BT[x & 1].query(*pre + 1, *nxt - 1);
    }
    else{
        return (x - *pre + 1) & 1 && (*nxt - x + 1) & 1 ? a[x] : 0;
    }
}

inline void build(){
    s.insert(-1), s.insert(n + 2);
    s.insert(-1145141919), s.insert(1145141919);
    s.insert(1), s.insert(n);
    FOR(i, 2, n - 1) if(!((a[i - 1] < a[i]) ^ (a[i] >= a[i + 1]))) s.insert(i);
    for(reg iter it = s.begin(); it != s.end(); ++it) ans += get_num(it);
    return;
}

inline void update(int x, int y){
    reg iter nxt = s.upper_bound(x), pre = --s.lower_bound(x);
    ans -= get_num(nxt), ans -= get_num(pre);
    reg iter nnxt = nxt, ppre = pre;
    ++nnxt, --ppre;
    ans -= get_num(nnxt), ans -= get_num(ppre);
    if(*next(pre) == x) ans -= get_num(next(pre));
    
    BT[x & 1].update(x, y - a[x]);
    a[x] = y;
    FOR(i, x - 1, x + 1){
        if(i <= 1 || i >= n) continue;//边界也不需要从 set 里面取出来
        if(!((a[i - 1] < a[i]) ^ (a[i] >= a[i + 1]))) s.insert(i);
        else s.erase(i);
    }

    ++nnxt;
    for(reg iter it = ppre; it != nnxt; ++it){
        ans += get_num(it);
    }
    return;
}

int main(){
    n = read();
    FOR(i, 1, n) BT[i & 1].update(i, a[i] = read());
    build();
    m = read();
    Rint x, y;
    FOR(o, 1, m){
        x = read(), y = read();
        update(x, y);
        printf("%lld\n", ans);
    }
    return 0;
}