Codeforces Round 546 E

Posted on | In

link

首先，根据$ a_{i} + k_{i} \leq a_{i+1} $和$ a_{i+1} + k_{i+1} \leq a_{i+2} $有$ a_{i} \leq a_{i+1} - k_{i} \leq a_{i+2} - k_{i} - k_{i+1} $，依据此规律可以构造一个array $b$，其中$ b_1 = a_1, \space b_{i} = a_{i} - \sum_{j=1}^{i-1} k_{j} $

那么问题就变得简单了。

对array $b$，用线段树进行维护。

对于操作1，二分找到最后一个值小于$ b_{i} + x $的元素$ b_{j} $，将$ b_{i}, b_{i+1}, …, b{j} $修改为$ b_{i} + x $。
对于操作2，答案即为$ \sum_{i=l}^{r} \sum_{j=1}^{i-1} k_{j} + \sum_{i=l}^{r} b_{i}$。

Code:

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

struct Node {
  ll v, lazy;
  bool cov;
  Node() { v = lazy = 0; cov = false; }
} T[maxn << 2];

ll a[maxn], k[maxn];

void build(int i, int l, int r) {
  if (l == r) {
    T[i].v = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  T[i].v = T[i << 1].v + T[i << 1 | 1].v;
}

void pushdown(int i, int l, int r) {
  if (T[i].cov) {
    int m = (l + r) / 2, ls = (m - l + 1), rs = (r - m);
    T[i << 1].v = T[i].lazy * ls;
    T[i << 1 | 1].v = T[i].lazy * rs;
    T[i << 1].lazy = T[i << 1 | 1].lazy = T[i].lazy;
    T[i << 1].cov = T[i << 1 | 1].cov = true;
    T[i].cov = false;
  }
}

void modify(int L, int R, ll x, int i, int l, int r) {
  if (L > R || l > r) return;
  if (L <= l && r <= R) {
    T[i].v = (r - l + 1) * x;
    T[i].lazy = x, T[i].cov = true;
    return;
  }
  pushdown(i, l, r);
  int mid = (l + r) / 2;
  if (R <= mid) modify(L, R, x, i << 1, l, mid);
  else if (mid < L) modify(L, R, x, i << 1 | 1, mid + 1, r);
  else {
    modify(L, R, x, i << 1, l, mid);
    modify(L, R, x, i << 1 | 1, mid + 1, r);
  }
  T[i].v = T[i << 1].v + T[i << 1 | 1].v;
}

ll query(int L, int R, int i, int l, int r) {
  if (L <= l && r <= R) {
    return T[i].v;
  }
  pushdown(i, l, r);
  int mid = (l + r) / 2;
  if (R <= mid) return query(L, R, i << 1, l, mid);
  else if (mid < L) return query(L, R, i << 1 | 1, mid + 1, r);
  else {
    return query(L, R, i << 1, l, mid) + query(L, R, i << 1 | 1, mid + 1, r);
  }
}

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

  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 2; i <= n; i++) {
    cin >> k[i], k[i] += k[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    a[i] -= k[i];
  }
  for (int i = 1; i <= n; i++) {
    k[i] += k[i - 1];
  }
  build(1, 1, n);
  int q; cin >> q;
  while (q--) {
    char opt; cin >> opt;
    if (opt == '+') {
      int p, x; cin >> p >> x;
      ll v = query(p, p, 1, 1, n) + x;
      int r = 0;
      for (int i = 17; i >= 0; i--) {
        int pos = r | (1 << i);
        if (pos > n || pos == 0) {
          continue;
        }
        if (query(pos, pos, 1, 1, n) < v) {
          r |= (1 << i);
        }
      }
      modify(p, r, v, 1, 1, n);
    } else {
      int l, r; cin >> l >> r;
      cout << query(l, r, 1, 1, n) + k[r] - k[l - 1] << "\n";
    }
  }
}