// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct stmnmx {
static const int Nmax = 1e6 + 42;
int Nst;
int st[Nmax * 4];
int id = 0;
#define mnmx min
void init_(int v, int tl, int tr) {
if(tl == tr) st[v] = id;
else {
int tm = (tl + tr) / 2;
init_((v << 1), tl, tm);
init_((v << 1) + 1, tm + 1, tr);
st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
}
}
void init(int N) {
Nst = N;
init_(1, 0, Nst - 1);
}
int get_(int l, int r, int v, int tl, int tr) {
if(l > r) return id;
if(l == tl && r == tr) return st[v];
int tm = ((tl + tr) >> 1);
return mnmx(get_(l, min(r, tm), (v << 1), tl, tm), get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr));
}
int get(int l, int r) {
return get_(l, r, 1, 0, Nst - 1);
}
void upd_(int pos, int new_v, int v, int tl, int tr) {
if(tl == tr) st[v] = new_v;
else {
int tm = ((tl + tr) >> 1);
if(pos <= tm) upd_(pos, new_v, (v << 1), tl, tm);
else upd_(pos, new_v, (v << 1) + 1, tm + 1, tr);
st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
}
}
void upd(int pos, int new_v) {
return upd_(pos, new_v, 1, 0, Nst - 1);
}
};
struct stsum {
int Nst;
vector<ll> st;
void init_(int v, int tl, int tr) {
if(tl == tr) st[v] = 0;
else {
int tm = (tl + tr) / 2;
init_((v << 1), tl, tm);
init_((v << 1) + 1, tm + 1, tr);
st[v] = 0;
}
}
void init(int n) {
Nst = n;
st.resize(4 * n);
init_(1, 0, Nst - 1);
}
ll get_(int l, int r, int v, int tl, int tr) {
if(l > r) return 0;
if(l == tl && r == tr) return st[v];
int tm = ((tl + tr) >> 1);
return get_(l, min(r, tm), (v << 1), tl, tm) + get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr);
}
ll get(int l, int r) {
return get_(l, r, 1, 0, Nst - 1);
}
void set_(int pos, ll value, int v, int tl, int tr) {
if(tl == tr) st[v] = value;
else {
int tm = ((tl + tr) >> 1);
if(pos <= tm) set_(pos, value, (v << 1), tl, tm);
else set_(pos, value, (v << 1) + 1, tm + 1, tr);
st[v] = st[(v << 1)] + st[(v << 1) + 1];
}
}
void set(int pos, ll value) {
set_(pos, value, 1, 0, Nst - 1);
}
void add_(int pos, ll delta, int v, int tl, int tr) {
if(tl == tr) st[v] += delta;
else {
int tm = ((tl + tr) >> 1);
if(pos <= tm) add_(pos, delta, (v << 1), tl, tm);
else add_(pos, delta, (v << 1) + 1, tm + 1, tr);
st[v] = st[(v << 1)] + st[(v << 1) + 1];
}
}
void add(int pos, ll delta) {
add_(pos, delta, 1, 0, Nst - 1);
}
int get_by_order_(int v, int tl, int tr, int k) {
if(tl == tr) return tl;
int tm = (tl + tr) / 2;
if(st[(v << 1)] >= k) return get_by_order_((v << 1), tl, tm, k);
else return get_by_order_((v << 1) + 1, tm + 1, tr, k - st[(v << 1)]);
}
int get_by_order(int k) {
return get_by_order_(1, 0, Nst - 1, k + 1);
}
};
void solve() {
int n, q;
cin >> n;
string s; cin >> s;
cin >> q;
string rs = s; reverse(all(rs));
s += rs;
n *= 2;
vector<int> pref(n + 1), amT(n + 1);
vector<int> posT(n + 1, -1);
stmnmx st; st.init(n + 1);
for(int i = 0; i < n; i++) {
amT[i + 1] = amT[i] + (s[i] == 'T');
if(posT[amT[i + 1]] == -1) posT[amT[i + 1]] = i + 1;
pref[i + 1] = pref[i] + (s[i] == 'C' ? 1 : -1);
st.upd(i + 1, pref[i + 1]);
}
while(q--) {
int l, r;
cin >> l >> r;
int mn1 = st.get(l, r) - pref[l - 1];
int take1 = 0, take2 = 0;
if(mn1 < 0) take1 = -mn1;
if(take1 == amT[r] - amT[l - 1]) { cout << take1 << '\n'; continue; }
int pref1 = pref[r] - pref[l - 1] + take1;
int l2 = -1, r2 = -1;
if(take1 == 0) {
l2 = n - r + 1;
r2 = n - l + 1;
} else {
int haveT = amT[l - 1];
int needT = haveT + take1;
int pos_needT = posT[needT];
pos_needT++;
l2 = n - r + 1;
r2 = n - pos_needT + 1;
}
int mn2 = st.get(l2, r2) - pref[l2 - 1];
if(mn2 < 0) take2 = -mn2;
cout << take1 + take2 << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
/*
+++------++ ++------+++
1 2 3 2 1 0 -1 -2 -3 -2 -1 | 0 1 0 -1 -2 -3 -4 -5 -4 -3 -2
1 2 3 2 1 0 -1 -2 -3 -2 -1 | 0 1 0 -1 -2 -3 -4 -5 -4 -3 -2
CCCXXXXTTTCC CCTTTXXXCCC
?
*/
Compilation message
election.cpp: In function 'void solve()':
election.cpp:141:9: warning: unused variable 'pref1' [-Wunused-variable]
141 | int pref1 = pref[r] - pref[l - 1] + take1;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
