#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mx = 1.2e5 + 5;
const int magic = 350;
//const int magic = 3;
namespace rmq {
struct segtree {
segtree* lc = 0, * rc = 0;
int l, r;
int v = numeric_limits<int>::max();
segtree* getmem();
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r) {
if (l == r)return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
};
segtree* upd(int qi, int qv) {
segtree* tr = getmem(); *tr = *this;
if (qi < l || qi > r) return tr;
if (l == r) { tr->v = qv; return tr; }
tr->lc = lc->upd(qi, qv); tr->rc = rc->upd(qi, qv);
tr->v = min(tr->lc->v, tr->rc->v);
return tr;
}
int q(int ql, int qr) {
if (ql > qr)return numeric_limits<int>::max();
if (ql > r || qr < l) return numeric_limits<int>::max();
if (ql <= l && qr >= r) return v;
return min(lc->q(ql, qr), rc->q(ql, qr));
}
}mem[mx * 36]; int memsz = 0;// surely enogh?
segtree* segtree::getmem() { return &mem[memsz++]; }
}
namespace rsq {
struct segtree {
segtree* lc = 0, * rc = 0;
int l, r;
int v = 0;
segtree* getmem();
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r) {
if (l == r)return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
};
segtree* upd(int qi, int qv) {
segtree* tr = getmem(); *tr = *this;
if (qi < l || qi > r) return tr;
if (l == r) { tr->v += qv; return tr; }
tr->lc = lc->upd(qi, qv); tr->rc = rc->upd(qi, qv);
tr->v = tr->lc->v + tr->rc->v;
return tr;
}
int q(int ql, int qr) {
if (ql > qr) return 0;
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return v;
return lc->q(ql, qr) + rc->q(ql, qr);
}
}mem[mx * 72]; int memsz = 0;// surely enogh?
segtree* segtree::getmem() { return &mem[memsz++]; }
}
struct bit {
vector<int> b, a;
bit(int n) : b(n + 1, 0), a(n + 1, 0) {};
int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i]; return v; }
void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
void u(int l, int r, int v) { if (l > r) return; u(l, v); u(r + 1, -v); }
};
int32_t main() {
int n, m; cin >> n >> m;
string c; cin >> c;
vector<int> a(m); for (auto& x : a) { cin >> x; x--; }
vector<vector<int>> a2(n + 1);
for (int i = 0; i < m; i++) a2[a[i]].push_back(i);
vector<int> ls, rs;
ls.push_back(-1); rs.push_back(n);
for (int i = 0; i < n; i++) if (c[i] == 'B') ls.push_back(i);
for (int i = n - 1; i >= 0; i--) if (c[i] == 'R') rs.push_back(i);
vector<int> pre(n, 0);
for (int i = 0; i < n; i++) {
if (i) pre[i] = pre[i - 1];
pre[i] += c[i] == 'R';
}
auto sm = [&](int l, int r) {
if (l > r) return 0LL;
if (l > n) l = n;
if (r > n - 1) r = n - 1;
if (r < 0) return 0LL;
if (l <= 0) return pre[r];
return pre[r] - pre[l - 1];
}; //very necessary yk
rmq::segtree* tmp = new rmq::segtree(0, n - 1);
vector<rmq::segtree*> ac(m, 0);
for (int i = m - 1; i >= 0; i--) {
ac[i] = tmp = tmp->upd(a[i], i);
//cout << ac[i]->v << endl;
}
rsq::segtree* tmp2 = new rsq::segtree(0, m - 1);
vector<rsq::segtree*> ac2(n + 1, 0);
for (int i = 0; i <= n; i++) {
for (auto& x : a2[i]) tmp2 = tmp2->upd(x, i + 1);
ac2[i] = tmp2;
}
rsq::segtree* tmp3 = new rsq::segtree(0, m - 1);
vector<rsq::segtree*> ac3(n + 1, 0);
for (int i = n; i >= 0; i--) {
for (auto& x : a2[i]) {
tmp3 = tmp3->upd(x, n - 1 - i);
// if (x >= 5 && x <= 7) {
// //cout << "owo" << x << "," << i << endl;
// cout << tmp3->v << "," << tmp3->q(5, 7) << endl;
// }
}
ac3[i] = tmp3;
}
//cout << "BRUH " << ac2[2]->q(5, 7) << "," << ac3[3]->q(5, 7) << endl;
int holy[magic][mx];
for (int j = 0; j + magic <= m; j += magic) {
int k = j / magic;
bit die(n + 1);
//cout << j << endl;
for (int i = 0; i <= n; i++) die.u(i, i, i);
for (int x = j; x < j + magic; x++) {
int cur = 0;
while (cur <= n) {
if(0){
int i = die.q(cur) / (n + 1);
int l = cur - 1, r = n + 1;
while (r - l > 1) {
int m = l + (r - l) / 2;
if (die.q(m) / (n + 1) == i) l = m;
else r = m;
}
//[cur, l] is bound
int l2 = cur - 1, r2 = l + 1;
while (r2 - l2 > 1) {
int m = l2 + (r2 - l2) / 2;
if (die.q(m) % (n + 1) >= a[x]) r2 = m;
else l2 = m;
}
//r is bound
die.u(r2, l, 1);
cur = l + 1;
}
else{
if(die.q(cur) >= a[x]) die.upd(cur, cur, 1);
cur++;
}
}
die.u(0, n, a[x] + 1);
//for (int i = 0; i <= n; i++) cout << die.q(i) << ",";
//cout << endl;
}
for (int i = 0; i <= n; i++) {
if (i) die.a[i] += die.a[i - 1];
holy[k][i] = die.a[i] % (n + 1);
}
}
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r; l--;r--;
//solve
int li = -1, ri = n;
int cur = l;
auto qcnt = [&](int l, int r) {
//cout << "q " << l << "," << r << "," << li << "," << ri << endl;
int res = 0;
if (l > r) return 0LL;
if (r <= li) return r - l + 1;
if (l >= ri) return 0LL;
if (l <= li) {
res += li - l + 1;
l = li + 1;
}
if (r >= ri) r = ri - 1;
//cout << "fk" << l << "," << r << "," << res << endl;
return res + sm(l, r);
//LMAO
};
auto qcnt2 = [&](int l, int r) {
if (l > r) return 0LL;
return (r - l + 1) - qcnt(l, r);};
auto thing = [&](int t) { // should work for everything?
//cout << "br" << t << endl;
int a = qcnt(0, t - 1) * 2 + 1;
int b = qcnt2(t + 1, n - 1) * 2;
//cout << a << "|" << b << endl;
if (a > b) {
int ll = 0 - 1, rr = t + 1;
while (rr - ll > 1) {
int m = ll + (rr - ll) / 2;
if (qcnt(m, t - 1) * 2 + 1 >= b)ll = m;
else rr = m;
}
ri = min(ri, ll);
if (li >= ri) li = ri - 1;
} else {
int ll = t, rr = n;
while (rr - ll > 1) {
int m = ll + (rr - ll) / 2;
//cout << ll << "," << rr << "," << m << endl;
if (qcnt2(t + 1, m) * 2 >= a)rr = m;
else ll = m;
}
li = rr;
if (ri <= li) ri = li + 1;
}
};
auto test = [&](int t) -> bool {
//cout << "Bad" << t << endl;
//cout << "how" << li << "," << ri << endl;
int v1 = li == -1 ? 0 : ac2[li]->q(cur, t);
//cout << "que" << endl;
int v2 = ri == n ? 0 : ac3[ri]->q(cur, t);
// cout << cur << "," << li << "," << ri << "," << t << "," << v1 << "," << v2 << endl;
//cout << "nah" << endl;
int tmp1 = prev(upper_bound(ls.begin(), ls.end(), li)) - ls.begin();
int tmp2 = prev(upper_bound(rs.begin(), rs.end(), ri, greater<int>())) - rs.begin();
if (tmp1 + v1 >= ls.size()) return false;
if (tmp2 + v2 >= rs.size()) return false;
if (ls[tmp1 + v1] >= rs[tmp2 + v2]) return false;
if (v1)li = ls[tmp1 + v1];
if (v2)ri = rs[tmp2 + v2];
cur = t + 1;
return true;
};
while (cur <= r) {
//cout << ac[cur]->q(li + 1, ri - 1) << endl;
//cout << "die " << cur << "," << li + 1 << "," << ri - 1 << "," << r << endl;
int t = min(ac[cur]->q(li + 1, ri - 1), r + 1);
//do the thing?
if (!test(t - 1)) break;
//cout << "hi " << li << "," << ri << endl;
//cout << "hell " << cur << "," << a[cur] << endl;
//cout << "asdf " << li << "," << ri << "," << cur << endl;
if (cur <= r)thing(a[cur++]);
// cout << "asdf2 " << li << "," << ri << "," << cur << endl;
}
//cout << "asdf3 " << li << "," << ri << "," << cur << endl;
//cout << "broke" << endl;
if (cur <= r) {
int t = min(ac[cur]->q(li + 1, ri - 1), r + 1);
//cout << "T IS " << t << endl;
for (int i = 18; i >= 0; i--) {
if (cur + i <= t - 1) test(cur + i);
}
//cout << "asdf4 " << li << "," << ri << "," << cur << endl;
//if (cur <= r)cout << "no" << endl;
}
if (cur <= r) thing(a[cur++]);
//cout << li << "," << ri << "," << cur << endl;
while (cur <= r) {
if (cur % magic == 0 && cur + magic <= r + 1) {
//cout << cur << "," << magic << "," << ri << "," << holy[cur / magic][ri] << endl;
ri = holy[cur / magic][ri];
li = ri - 1;
cur += magic;
} else {
//cout << "br" << "," << cur << "," << a[cur] << endl;
if (a[cur] >= ri) ri++;
ri += a[cur] + 1; ri %= (n + 1);
li = ri - 1;
cur++;
}
//cout << li << "," << ri << "," << cur << endl;
//cout << ri << endl;
}
cout << qcnt(0, n - 1) << endl;
//if (cur <= r)cout << "yes" << endl;
//cout << li << "," << ri << endl;
//if (cur <= r) cout << "ans: " << (li + ac2[n - 1]->q(cur, r)) % (n + 1) << endl;
//else cout << "ans: " << qcnt(0, n - 1) << endl;
}
}
Compilation message
Main.cpp: In member function 'void bit::u(long long int, long long int)':
Main.cpp:76:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
| ~~^~~~~~~~~~
Main.cpp:76:69: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | void u(int i, int v) { if (i < a.size()) a[i] += v; for (i++; i < b.size(); i += i & -i) b[i] += v; }
| ~~^~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:165:48: error: 'struct bit' has no member named 'upd'
165 | if(die.q(cur) >= a[x]) die.upd(cur, cur, 1);
| ^~~
Main.cpp: In lambda function:
Main.cpp:243:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
243 | if (tmp1 + v1 >= ls.size()) return false;
| ~~~~~~~~~~^~~~~~~~~~~~
Main.cpp:244:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | if (tmp2 + v2 >= rs.size()) return false;
| ~~~~~~~~~~^~~~~~~~~~~~
