Codeforces Round 775

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
D(二分，单调队列，前缀和，线段树，区间覆盖，动态规划)

D

https://codeforces.com/contest/1648/problem/D

3xn 左上角 走到 右下角，只能右和下两个方向的走，价值= 经过块的值的和

第一行，第三行直接可走，第二行需要额外代价v,开启[l,r]一段

问总获得价值最大值

范围

n <= 5e5

块上值 -1e9 ~ 1e9

可选扩展 5e5 个，扩展代价 1~1e9

题解

行走代价简化

走过的样子无非是

1
2
3
xxxxxx
     xxxxxxx
           xxxxxxxxx

拆分一下,

第一段： 第一行+，第二行-

第二段： 第二行+，第三行+

1
2
3
4
5
6
     i
++++++
-----
            j
+++++++++++++
            +++++++++

那么行走代价为s[i]+t[j]

剩下就是开放(i,j)的最小代价

状态与转移与范围最值

考虑从(1,1)走到(2,i), 其中当前使用的最右侧的开放端点是i

1
2
3
4
5
6
     ?
xxxxxx      i
     xxxxxxxx
        [   ]
      [  ]
    [  ]

dp[i] = (1,1) -> (2,i) 且i 是当前最右侧开放的点, 上述条件下 , 最大的 s[?] - cost(?,i)

这里两点

  1. i 是某个区间右侧端点, 且走到了这个位置
  2. dp表示的是这样范围中最大的, 包含s 和 cost , 这里很神奇，没有t意味着，下面转移时并不用考虑第二行所选位置对dp的影响

也就是一个准确，一个范围最值

状态转移，

要么是通过第一行直接进入所选区间走到i,

要么就是先走到(2,j), 再在一个区间内走到i, 所以 j 在 [l-1,r] 内

1
2
3
4
5
6
     ?
xxxxxx       j
     xxxxxxxxx
           [      ]
xxxxxx            i
     xxxxxxxxxxxxxx

dp[i] = max(dp[j] - cost(i,j).value)

剩下的就是最终的答案, 因为可能走到不是某个区间的终点，就去第三行了

1
2
3
4
5
     ?
xxxxxx         i  j
     xxxxxxxxxxxxxx
                  xxxxxxx
              [      ]

ans = max(dp[i] - cost(i,j).value + t[j])， i,j 在某个区间内，i < j, 对于相等的情况 上面直接+t[i]就更新

换个角度，先固定一个区间,cost确定,再在这个区间里找 max(dp[i]+t[j])

其中i 在[l-1,r]内

注意到上面的方案，一定经过了某个开放区间的终点，开放区间为 >= 1 个 ，所以还有一种情况，只开放了一个区间，i和j都在区间之中

上面最重要的是控制成了一个区间,但不一定是唯一一个区间

而上面的操作和只开放一个区间十分的像，都是开放一个区间，左dp[i],右t[j] 和(i < j) 左s[i],右t[j] (i <= j)

注意到对于左dp,右t的情况，i==j只会产生比最优更小的答案，所以可以考虑在最值处理时合并left[i] = min(dp[i],dp[i-1],s[i])

最后特化成只开放一个区间的问题

代码

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define SEG_ROOT 1,0,n-1
#define SEG_L o<<1,l,m
#define SEG_R o<<1|1,m+1,r
const double pi = acos(-1.0);
 
const int N = 500'000;
ll s[N + 10];
ll t[N + 10];
ll dp[N + 10];
ll a[3][N + 10];
vector<tuple<int, int, ll> > rlv;
 
ll seg[2][N * 4 + 10];
ll segans[N * 4 + 10];
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
ll query(int o, int l, int r, int ql, int qr) {
  if (l == ql && r == qr)
    return seg[0][o];
  int m = (l + r) / 2;
  if (qr <= m) {
    return query(SEG_L, ql, qr);
  } else if (ql > m) {
    return query(SEG_R, ql, qr);
  } else {
    return max(query(SEG_L, ql, m),
               query(SEG_R, m + 1, qr));
  }
}
 
void update(int o, int l, int r, int pos) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m)
    update(SEG_L, pos);
  else
    update(SEG_R, pos);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
void build(int o, int l, int r) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  build(SEG_L);
  build(SEG_R);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
// [l,r]为开放段
void buildans(int o, int l, int r) {
  if (l == r) {
    // 可以dp到[l-1] 或[l]
    seg[0][o] = max(max(dp[l], s[l]), l > 0 ? dp[l-1] : -INF);
    seg[1][o] = t[l];
    segans[o] = seg[0][o] + t[l];
    return;
  }
  int m = (l + r) / 2;
  buildans(SEG_L);
  buildans(SEG_R);
 
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
  seg[1][o] = max(seg[1][o << 1], seg[1][o << 1 | 1]);
  segans[o] = max(seg[0][o << 1] + seg[1][o << 1 | 1],
                  max(segans[o << 1], segans[o << 1 | 1]));
};
 
// {最大值, 最大dp, 最大t}
vector<ll> qans(int o, int l, int r, int ql, int qr) {
  if (ql == l && qr == r) {
    return {segans[o], seg[0][o], seg[1][o]};
  }
  int m = (l + r) / 2;
  if (qr <= m) {
    return qans(SEG_L, ql, qr);
  } else if (ql > m) {
    return qans(SEG_R, ql, qr);
  }
  auto lres = qans(SEG_L, ql, m);
  auto rres = qans(SEG_R, m + 1, qr);
  return {max(max(lres[0], rres[0]), lres[1] + rres[2]), max(lres[1], rres[1]),
          max(lres[2], rres[2])};
}
 
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  ll a2 = 0;
  rep(i, 0, 3) {
    rep(j, 0, n) { scanf("%lld", &a[i][j]); }
  }
  rep(i, 0, n) a2 += a[2][i];
  s[0] = a[0][0];
  rep(i, 1, n) { s[i] = s[i - 1] + a[0][i] - a[1][i - 1]; }
  t[0] = a2 + a[1][0];
  rep(i, 1, n) { t[i] = t[i - 1] + a[1][i] - a[2][i - 1]; }
 
  rep(i, 0, q) {
    int r, l;
    ll v;
    scanf("%d %d %lld", &l, &r, &v);
    rlv.pb({r - 1, l - 1, v});
  }
  ll ans = -INF;
  // 按右端点排序
  sort(rlv.begin(), rlv.end());
  // 处理 使用一次区间直接进入的
  vector<int> pos;  // 单调队列
  unsigned long itr = 0;
  rep(i, 0, n){
    dp[i] = -INF;
  }
  rep(i, 0, n) {  // 下标
    while (pos.size() && s[pos.back()] <= s[i]) {
      pos.pop_back();
    }
    pos.pb(i);
    while (itr < rlv.size() && get<0>(rlv[itr]) == i) {
      // 区间内最大值
      dp[i] = max(
          dp[i],
          s[*lower_bound(pos.begin(), pos.end(), get<1>(rlv[itr]))] -
              get<2>(rlv[itr]));  // cost > 0选自己没影响
      if (dp[i] != -INF) {
        ans = max(ans, dp[i] + t[i]);
        // printf("dp[%lld] => %lld\n", i, dp[i]);
      }
      itr++;
    }
  }
  build(SEG_ROOT);
  itr = 0;
  for(auto [r,l,v]:rlv){
    // 注意可以上一个结束的位置[?..l-1] 和当前 [l..r] 是相邻而不是重叠
    // dp[i] = max(dp[<i] - cost);
    ll newdpi = query(SEG_ROOT, max(0,l-1), max(0,r-1)) - v;
    if (newdpi > dp[r]) {
      dp[r] = newdpi;
      ans = max(ans, dp[r] + t[r]);
      // printf("update: dp[%lld] => %lld\n", i, dp[i]);
      update(SEG_ROOT, r);
    }
  }
  buildans(SEG_ROOT);
  // [l...r] => [l..m] [m+1,r]
  for (auto [r, l, v] : rlv) {
    auto qres = qans(SEG_ROOT, l, r);
    if (qres[0] <= -INF)
      continue;
    ans = max(ans, qres[0] - v);
  }
  printf("%lld\n", ans);
 
  return 0;
}

总结

一个核心的点就是区间覆盖，转换成刚好走到以某个区间结束的动规，感觉要是一个纯的动规还可能想到，合在一起竟然卡住了

参考

官方题解

C202044zxy

cggghh

Sstee1XD

某岛