#include <bits/stdc++.h>
#define x first
#define y second
using ll = long long;
using namespace std;
const int N = 1 << 17, M = 1 << 17, A = 11;
int st[2 * N], lazy[2 * N], a[N], b[M], st1[3 * M][A], fre = 3 * M - 2;
void build() {
for (int i = N - 1; i < 2 * N - 1; i++) {
st[i] = a[i - N + 1];
lazy[i] = -1;
}
for (int i = N - 2; i >= 0; i--) {
st[i] = st[2 * i + 1] + st[2 * i + 2];
lazy[i] = -1;
}
}
void update_seg(int l, int r, int v, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
st[i] = v * (r1 - l1 + 1);
lazy[i] = v;
return;
}
if (l1 > r || r1 < l) {
return;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
update_seg(l, r, v, l1, (l1 + r1) / 2, 2 * i + 1);
update_seg(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
st[i] = st[2 * i + 1] + st[2 * i + 2];
}
int get_sum(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
return st[i];
}
if (l1 > r || r1 < l) {
return 0;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
return get_sum(l, r, l1, (l1 + r1) / 2, 2 * i + 1) + get_sum(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
}
int down_l(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 > r || r1 < l) {
return -1;
}
if (s > st[i] || s < 0) {
return -1;
}
if (l1 == r1 && s == st[i] && l1 >= l && r1 <= r) {
return l1;
} else if (l1 == r1) {
return -1;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
int v = get_sum(max(l, (l1 + r1) / 2 + 1), min(r, r1));
int left = down_l(l, r, s - v, l1, (l1 + r1) / 2, 2 * i + 1);
if (left == -1) {
return down_l(l, r, s, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
}
return left;
}
int down_r(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 > r || r1 < l) {
return -1;
}
if (s > r1 - l1 + 1 - st[i] || s < 0) {
return -1;
}
if (l1 == r1 && s == 1 - st[i] && l1 >= l && r1 <= r) {
return l1;
} else if (l1 == r1) {
return -1;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
int v = max(min(r, (l1 + r1) / 2) - max(l, l1) + 1 - get_sum(max(l, l1), min(r, (l1 + r1) / 2)), 0);
int right = down_r(l, r, s - v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
if (right == -1) {
return down_r(l, r, s, l1, (l1 + r1) / 2, 2 * i + 1);
}
return right;
}
void merge(int to, int a, int b) {
for (int i = 0; i < A; i++) {
st1[to][i] = st1[b][st1[a][i]];
}
}
int get_ans(int l, int r, int l1 = 0, int r1 = M - 1, int i = 0) {
if (l1 > r || r1 < l) {
return 3 * M - 1;
}
if (l1 >= l && r1 <= r) {
for (int j = 0; j < A; j++) {
st1[fre][j] = st1[i][j];
}
return fre--;
}
int ans = fre--;
merge(ans, get_ans(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_ans(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
return ans;
}
int32_t main() {
int n, m;
for (int i = 0; i < A; i++) {
st1[3 * M - 1][i] = i;
}
cin >> n >> m;
string as;
cin >> as;
for (int i = 0; i < n; i++) {
a[i] = as[i] == 'B' ? 0 : 1;
}
for (int i = 0; i < m; i++) {
cin >> b[i]; b[i]--;
}
// cout << "!!\n";
int q;
cin >> q;
if (n != 10) {
while (q--) {
int l, r;
cin >> l >> r; l--; r--;
build();
// cout << "!\n";
for (int i = l; i <= r; i++) {
int sl = get_sum(0, b[i] - 1), sr = n - b[i] - 1 - get_sum(b[i] + 1, n - 1);
// cout << sl << ' ' << sr << '\n';
if (sl < sr) {
int gr = down_r(b[i] + 1, n - 1, sl + 1);
// cout << "! " << gr << '\n';
update_seg(0, gr, 1);
} else {
int gr = down_l(0, b[i] - 1, sr);
// cout << "! " << gr << '\n';
if (gr == -1) {
gr = b[i];
}
update_seg(gr, n - 1, 0);
}
}
cout << st[0] << '\n';
}
} else {
int pr[A][A];
build();
for (int i = 0; i < n; i++) {
update_seg(0, n - 1, 0);
for (int j = 0; j < A; j++) {
update_seg(0, j - 1, 1);
int sl = get_sum(0, i - 1), sr = n - i - 1 - get_sum(i + 1, n - 1);
if (sl < sr) {
int gr = down_r(i + 1, n - 1, sl + 1);
pr[i][j] = max(gr + 1, j);
} else {
int gr = down_l(0, i - 1, sr);
if (gr == -1) {
gr = i;
}
pr[i][j] = min(gr, j);
}
// cout << pr[i][j] << ' ';
}
// cout << '\n';
}
for (int i = M - 1; i < 2 * M - 1; i++) {
if (i - M + 1 < m) {
for (int j = 0; j < A; j++) {
st1[i][j] = pr[b[i - M + 1]][j];
}
} else {
for (int j = 0; j < A; j++) {
st1[i][j] = j;
}
}
}
for (int i = M - 1; i >= 0; i--) {
merge(i, 2 * i + 1, 2 * i + 2);
}
while (q--) {
int l, r;
cin >> l >> r; l--; r--;
fre = 3 * M - 2;
cout << st1[get_ans(l, r)][10] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3672 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3672 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3672 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
297 ms |
18188 KB |
Output is correct |
| 3 |
Correct |
295 ms |
18116 KB |
Output is correct |
| 4 |
Incorrect |
314 ms |
18276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
297 ms |
18188 KB |
Output is correct |
| 3 |
Correct |
295 ms |
18116 KB |
Output is correct |
| 4 |
Incorrect |
314 ms |
18276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
297 ms |
18188 KB |
Output is correct |
| 3 |
Correct |
295 ms |
18116 KB |
Output is correct |
| 4 |
Incorrect |
314 ms |
18276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3672 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
