题意
见原题中文题面
思路
首先考虑 O(nq)，可以令 dpi 表示当前取到了第 i 个点的答案，可以使用滑动窗口转移。对于必选的点可以考虑清空队列实现。
尝试优化，发现 k≤3×103，考虑 O(qk) 做法。
将 O(nq) 做法中的 dp 正反跑两遍。由于修改独立，对于每一次修改可以将答案分为前后两部分，对于修改位置后面的部分储存前缀 min，然后枚举小于修改位置的部分，这部分是 O(k) 的。
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
| #include <bits/stdc++.h>
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
mt19937 rnd(1209);
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
int n, k, dp[2][N];
int mn[N];
int q[N], a[N];
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
string s; cin >> s; s = "Y" + s;
int hh = 1, tt = 1; q[1] = 0;
for(int i = 1; i <= n; i ++)
{
while(hh <= tt && q[hh] < i - k) hh ++;
dp[0][i] = dp[0][q[hh]] + a[i]; if(s[i] == '1') hh = tt + 1;
while(hh <= tt && dp[0][q[tt]] >= dp[0][i]) tt --; q[++ tt] = i;
}
hh = 1, tt = 1; q[1] = n + 1; dp[1][n + 1] = 0;
for(int i = n; i; i --)
{
while(hh <= tt && q[hh] > i + k) hh ++;
dp[1][i] = dp[1][q[hh]] + a[i]; if(s[i] == '1') hh = tt + 1;
while(hh <= tt && dp[1][q[tt]] >= dp[1][i]) tt --; q[++ tt] = i;
}
int t; cin >> t;
while(t --)
{
int pos, x; cin >> pos >> x;
int up = min(n + 1, pos + k), ans = INF;
mn[pos] = dp[1][pos] - a[pos] + x;
for(int i = pos; i <= pos + k && i <= n + 1; i ++)
{
if(i != pos) mn[i] = min(mn[i - 1], dp[1][i]);
if(s[i] == '1') {up = i; break;}
}
for(int i = pos - 1; i >= pos - k && i >= 0; i --)
{
chmin(ans, dp[0][i] + mn[min(i + k, up)]);
if(s[i] == '1') break;
}
cout << ans << "\n";
}
}
fish main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t --) solve();
return 0;
}
|
