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
| #include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <deque>
#include <algorithm>
#define N 500005
typedef long long int ll;
int n, k, a[N]; char s[N]; ll f[N], g[N], tf[N], tg[N];
inline void solve() {
a[0] = a[n + 1] = 0; std::deque<int> dq;
memset(f, 0x3f, sizeof(f)); f[0] = 0; dq.push_back(0);
for(int i = 1; i <= n + 1; ++i) {
while(dq.size() && dq.front() < std::max(0, i - k)) dq.pop_front();
f[i] = f[dq.front()] + a[i];
while(dq.size() && f[dq.back()] >= f[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
for(int i = 0; i <= n + 1; ++i) tf[i] = f[i];
dq.clear();
memset(g, 0x3f, sizeof(g)); g[n + 1] = 0; dq.push_back(n + 1);
for(int i = n; i >= 0; --i) {
while(dq.size() && dq.front() > std::min(n + 1, i + k)) dq.pop_front();
g[i] = g[dq.front()] + a[i];
while(dq.size() && g[dq.back()] >= g[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
for(int i = 0; i <= n + 1; ++i) tg[i] = g[i];
}
inline ll query(int p, int v) {
std::deque<int> dq;
tf[p] += v - a[p];
for(int i = std::max(0, p - k); i <= p; ++i) {
while(dq.size() && tf[dq.back()] >= tf[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
for(int i = std::min(n + 1, p + 1); i <= std::min(n + 1, p + k); ++i) {
while(dq.size() && dq.front() < std::max(0, i - k)) dq.pop_front();
tf[i] = tf[dq.front()] + a[i];
while(dq.size() && tf[dq.back()] >= tf[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
dq.clear();
tg[p] += v - a[p];
for(int i = std::min(n + 1, p + k); i >= p; --i) {
while(dq.size() && tg[dq.back()] >= tg[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
for(int i = std::max(0, p - 1); i >= std::max(0, p - k); --i) {
while(dq.size() && dq.front() > std::min(n + 1, i + k)) dq.pop_front();
tg[i] = tg[dq.front()] + a[i];
while(dq.size() && tg[dq.back()] >= tg[i]) dq.pop_back();
if(s[i] == '1') while(dq.size()) dq.pop_back();
dq.push_back(i);
}
ll ans = LLONG_MAX;
for(int i = std::max(0, p - k); i <= std::min(n + 1, p + k); ++i) {
ans = std::min(ans, tf[i] + tg[i] - ((i ^ p) ? a[i] : v));
}
for(int i = p; i <= std::min(n + 1, p + k); ++i) tf[i] = f[i];
for(int i = p; i >= std::max(0, p - k); --i) tg[i] = g[i];
return ans;
}
int main() {
int t; scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
scanf("%s", s + 1); solve();
int q; scanf("%d", &q);
while(q--) {
int p, v; scanf("%d %d", &p, &v);
printf("%lld\n", query(p, v));
}
}
return 0;
}
|