DDOSvoid's Blog

CF 1136E Nastya Hasn't Written a Legend

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/CF1136E

简要题意：给定一个长度为 $n$ 的数列 $a_i$ 以及一个长度为 $n-1$ 的数列 $b_{i}$，现在有两种操作，第一种操作是给定 $x$ 和 $y$，首先将 $a_x$ 加上 $y$，如果 $a_{x+1}<a_x+b_x$，那么将 $a_{x+1}$ 变成 $a_x+b_x$，接着如果 $a_{x+2}<a_{x+1}+b_{x+1}$，将 $a_{x+2}$ 变成 $a_{x+1}+b_{x+1}$，以此类推，直至不满足条件；第二种操作是求 $\sum_{i=l}^ra_i$

$n,m\le 10^5$

Solution

注意到第一个不满足条件的右端点是可以二分的，另外我们注意如果修改区间是 $[l,r]$，我们可以将整个修改看成是区间覆盖，因为每个位置的数都是已知的，所以用线段树维护即可

时间复杂度为 $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
#include <iostream>
#include <vector>
#include <queue>
#define maxn 100010
#define INF 1000000000000000000
#define ll long long
using namespace std;

int n, m, a[maxn], b[maxn];
ll s[maxn], ss[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll v, mem;
} T[maxn * 4]; 
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }

void build(int i, int l, int r) {
    T[i].mem = INF;
    if (l == r) return T[i].v = a[l], void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update(int i, int l, int r, ll mem) {
    T[i].v = (r - l + 1) * mem + ss[r] - ss[l - 1];
    T[i].mem = mem;
}

inline void pushdown(int i, int l, int r) {
    ll &mem = T[i].mem; int m = l + r >> 1; if (mem == INF) return ;
    Update(lc, l, m, mem); Update(rc, m + 1, r, mem);
    mem = INF;
}

void update(int i, int l, int r, int L, int R, ll v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, l, r, v);
    int m = l + r >> 1; pushdown(i, l, r);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1; pushdown(i, l, r); 
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R); 
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    int l = x + 1, r = n, mid, ans = x; ll v = query(1, 1, n, x, x); 
    while (l <= r) {
        mid = l + r >> 1;
        if (query(1, 1, n, mid, mid) < v + y + s[mid] - s[x]) ans = mid, l = mid + 1;
        else r = mid - 1; 
    } update(1, 1, n, x, ans, v + y - s[x]); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    cout << query(1, 1, n, x, y) << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2; i <= n; ++i) cin >> b[i];
    for (int i = 2; i <= n; ++i) s[i] = s[i - 1] + b[i], ss[i] = ss[i - 1] + s[i];
    cin >> m; build(1, 1, n); 
    for (int i = 1; i <= m; ++i) { 
        char c[10]; cin >> c;
        if (c[0] == '+') solve_1();
        else solve_2();
    }
    return 0; 
}