#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct segtree {
int n;
vector<int> more;
vector<vector<int>> rem, frback, frfront;
segtree(int sz) {
n = 1;
while (n < sz) n *= 2;
more.resize(2 * n - 1);
rem.resize(2 * n - 1);
frback.resize(2 * n - 1);
frfront.resize(2 * n - 1);
}
int eq(char c) {
if (c == 'C') return 1;
if (c == 'T') return -1;
return 0;
}
void assign(int node, int l, int r, string& s) {
if (r != l + 1) {
int m = (l + r) / 2;
assign(node * 2 + 1, l, m, s);
assign(node * 2 + 2, m, r, s);
}
int here = 0;
for (int i = l; i < r; ++i) {
here += eq(s[i]);
more[node] += eq(s[i]);
if (here < 0) {
here = 0;
rem[node].push_back(i - l);
}
frfront[node].push_back((i == l ? 0 : frfront[node].back()) - eq(s[i]));
frfront[node].back() = max(frfront[node].back(), 0);
}
frback[node].resize(r - l + 1);
frback[node][r - l] = 0;
here = 0;
int idx = rem[node].size() - 1;
for (int i = r - 1; i >= l; --i) {
if (idx < 0 || i - l != rem[node][idx]) {
here += eq(s[i]);
} else --idx;
frback[node][i - l] = frback[node][i - l + 1] + (here < 0);
here = max(here, 0);
}
}
void assign(string& s) {
while (s.size() < n) s += '_';
assign(0, 0, n, s);
}
void getr(int node, int l, int r, int a, int b, vector<pair<int, pair<int, int>>>& ra) {
if (r <= a || l >= b) return;
if (a <= l && r <= b) {
ra.push_back({node, {l, r}});
return;
}
int m = (l + r) / 2;
getr(node * 2 + 1, l, m, a, b, ra);
getr(node * 2 + 2, m, r, a, b, ra);
}
int ans(int a, int b) {
vector<pair<int, pair<int, int>>> r;
getr(0, 0, n, a, b, r);
vector<int> remove(r.size());
int here = 0;
for (int i = 0; i < r.size(); ++i) {
remove[i] = rem[r[i].first].size();
remove[i] -= min(remove[i], here);
here += more[r[i].first] + remove[i];
}
here = 0;
int res = 0;
for (int i = r.size() - 1; i >= 0; --i) {
int ex;
int lunused = rem[r[i].first].size() - remove[i] - 1;
if (lunused == -1) ex = frback[r[i].first][0];
else {
ex = frfront[r[i].first][rem[r[i].first][lunused]];
ex += frback[r[i].first][rem[r[i].first][lunused] + 1];
}
ex -= min(ex, here);
remove[i] += ex;
res += remove[i];
here += more[r[i].first] + remove[i];
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
string s; cin >> s;
segtree st(n);
st.assign(s);
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
--l; --r;
cout << st.ans(l, r + 1) << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |