#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <set>
using namespace std;
// #define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
template <typename T = int>
inline T read() {
T s = 0, w = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') w = -1;
c = getchar();
}
while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
return s * w;
}
template <typename T>
inline void read(T &s) {
s = 0;
int w = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') w = -1;
c = getchar();
}
while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
s = s * w;
}
template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
read(x), read(arp...);
}
template <typename T>
inline void write(T x, char ch) {
if (x < 0) x = -x, putchar('-');
static char stk[25];
int top = 0;
do {
stk[top++] = x % 10 + '0', x /= 10;
} while (x);
while (top) putchar(stk[--top]);
putchar(ch);
return;
}
template <typename T>
inline void smax(T &x, T y) {
if (x < y) x = y;
}
template <typename T>
inline void smin(T &x, T y) {
if (x > y) x = y;
}
void quit() {
exit(0);
}
} using namespace FastIO;
const int N = 5e5 + 19;
int n, m, sum[N];
char s[N];
struct SegTree {
struct node { int t, lmax, rmax, tot; } g[N << 2];
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
node merge(node a, node b) {
return {max(max(a.t, b.t), a.rmax + b.lmax), max(a.lmax, a.tot + b.lmax), max(b.rmax, a.rmax + b.tot), a.tot + b.tot};
}
void build(int k, int l, int r) {
if (l == r) return g[k].t = g[k].lmax = g[k].rmax = max(0, sum[l]), g[k].tot = sum[l], void();
build(ls, l, mid); build(rs, mid+1, r);
g[k] = merge(g[ls], g[rs]);
}
node query(int k, int l, int r, int L, int R) {
if (L <= l && r <= R) return g[k];
if (R <= mid) return query(ls, l, mid, L, R);
if (L > mid) return query(rs, mid+1, r, L, R);
return merge(query(ls, l, mid, L, R), query(rs, mid+1, r, L, R));
}
} seg;
signed main() {
read(n); scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + (s[i] == 'C' ? 1 : -1);
seg.build(1, 1, n);
read(m); while (m--) {
int l, r; read(l, r);
write(seg.query(1, 1, n, l, r).t + sum[r] - sum[l-1], '\n');
}
return 0;
}
或者洛谷 P4786
