#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
string s;
struct c{
int a;
int b;
int dod;
};
struct d{
vector<c> swapy;
};
vector<int> krasnoludki;
const int MAXN = 2e5 + 5;
const int base = 1 << 17;
int ans[MAXN];
d drugaczesc[2 * base];
int M;
bool comp(const c &c1, const c &c2){
if(c1.a != c2.a){
return c1.a < c2.a;
}
return false;
}
int drugiwyn(int w, int a, int b, int akt_a, int akt_b, int curr){
if(a > b) return curr;
if(a <= akt_a and akt_b <= b){
int p = 0;
int k = drugaczesc[w].swapy.size() - 1;
while(p != k){
int sr = (p + k) / 2;
if(drugaczesc[w].swapy[sr].b < curr){
p = sr + 1;
}
else{
k = sr;
}
}
return (curr + drugaczesc[w].swapy[p].dod) % M;
}
if(akt_a > b or akt_b < a) return curr;
int mid = (akt_a + akt_b) / 2;
curr = drugiwyn(2 * w, a, b, akt_a, mid, curr);
curr = drugiwyn(2 * w + 1, a, b, mid + 1, akt_b, curr);
return curr;
}
struct e{
int sR;
int sB;
};
e strzalki[2 * base];
int iloscR(int w, int a, int b, int akt_a, int akt_b){
if(a > b) return 0;
if(a <= akt_a and akt_b <= b){
return strzalki[w].sR;
}
if(akt_a > b or akt_b < a) return 0;
int mid = (akt_a + akt_b) / 2;
return iloscR(2 * w, a, b, akt_a, mid) + iloscR(2 * w + 1, a, b, mid + 1, akt_b);
}
int iloscB(int w, int a, int b, int akt_a, int akt_b){
if(a > b) return 0;
if(a <= akt_a and akt_b <= b){
return strzalki[w].sB;
}
if(akt_a > b or akt_b < a) return 0;
int mid = (akt_a + akt_b) / 2;
return iloscB(2 * w, a, b, akt_a, mid) + iloscB(2 * w + 1, a, b, mid + 1, akt_b);
}
int ktaB(int w, int akt_a, int akt_b, int curr, int cel){
if(akt_a == akt_b) return akt_a;
int mid = (akt_a + akt_b) / 2;
if(strzalki[2 * w].sB + curr < cel){
return ktaB(2 * w + 1, mid + 1, akt_b, curr + strzalki[2 * w].sB, cel);
}
else{
return ktaB(2 * w, akt_a, mid, curr, cel);
}
}
int ktaR(int w, int akt_a, int akt_b, int curr, int cel){
if(akt_a == akt_b) return akt_a;
int mid = (akt_a + akt_b) / 2;
if(strzalki[2 * w + 1].sR + curr < cel){
return ktaR(2 * w, akt_a, mid, curr + strzalki[2 * w + 1].sR, cel);
}
else{
return ktaR(2 * w + 1, mid + 1, akt_b, curr, cel);
}
}
pair<int,int> dodajp(int pref, int suff, int ile, int n){
int pocz = pref;
int kon = n - suff + 1;
int v = iloscB(1, pocz + 1, kon - 1, 1, base);
if(ile >= v){
pocz = kon - 1;
ile -= v;
pocz = (pocz + ile) % M;
kon = pocz + 1;
return {pocz, n - pocz};
}
v = iloscB(1, 1, pocz, 1, base);
return {ktaB(1, 1, base, 0, v + ile + 1) - 1, suff};
}
pair<int,int> dodajk(int pref, int suff, ll ile, int n){
int pocz = pref;
int kon = n - suff + 1;
int v = iloscR(1, pocz + 1, kon - 1, 1, base);
//cout << pocz << " " << kon << " pk\n";
//cout << ile << " " << v << " il\n";
if(ile >= v){
//cout << suff << " " << ile + 1 << " si\n";
ile -= v;
//cout << pocz << " " << ile << " pi\n";
pocz = (pocz - ile + 2 * M) % M;
return {pocz, n - pocz};
}
v = iloscR(1, kon, base, 1, base);
return {pocz, n - ktaR(1, 1, base, 0, v + ile + 1)};
}
pair<int,int> dodajs(int pref, int suff, int mid, int n){
int pocz = pref;
int kon = n - suff + 1;
int iR1 = pref;
int iR2 = iloscR(1, pocz + 1, mid - 1, 1, base);
int iB1 = suff;
int iB2 = iloscB(1, mid + 1, kon - 1, 1, base);
int s1 = iR1 + iR2;
int s2 = iB1 + iB2;
//cout << s1 << " " << s2 << " s\n";
//cout << iB1 << " " << iB2 << " iB\n";
if(s1 >= s2){
if(s2 >= iR2){
pocz = pref - (s2 - iR2);
return {pocz, n - pocz};
}
else{
int v = iloscR(1, mid, base, 1, base);
return {pocz, n - ktaR(1, 1, base, 0, v + s2 + 1)};
}
}
else{
if(s1 + 1 >= iB2){
pocz = kon - 1 + (s1 - iB2 + 1);
return {pocz, n - pocz};
}
else{
int v = iloscB(1, 1, mid, 1, base);
return {ktaB(1, 1, base, 0, v + s1 + 2) - 1, suff};
}
}
}
struct zap{
int pref;
int suff;
int org;
int a;
int b;
};
vector<zap> queries;
vector<zap> nowe;
struct Node{
ll suma;
ll ile;
Node *l, *r;
Node(ll x, ll y) : ile(x), suma(y), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) : ile(ll->ile + rr->ile), suma(ll->suma + rr->suma), l(ll), r(rr) {}
};
Node *roots[MAXN];
Node *build(int akt_a = 1, int akt_b = base){
if(akt_a == akt_b) return new Node(0ll, 0ll);
int mid = (akt_a + akt_b) / 2;
return new Node(build(akt_a, mid), build(mid + 1, akt_b));
}
Node *add(Node *prev, ll val, int akt_a = 1, int akt_b = base){
if(akt_a == akt_b) return new Node(prev->ile + 1, prev->suma + val);
int mid = (akt_a + akt_b) / 2;
if(val <= mid){
return new Node(add(prev->l, val, akt_a, mid), prev->r);
}
else{
return new Node(prev->l, add(prev->r, val, mid + 1, akt_b));
}
}
pair<ll,ll> oblicz(Node *k, Node*p, int a, int b, int akt_a, int akt_b){
if(a <= akt_a and akt_b <= b){
return {k->ile - p->ile, k->suma - p->suma};
}
if(akt_a > b or akt_b < a) return {0ll, 0ll};
int mid = (akt_a + akt_b) / 2;
auto v1 = oblicz(k->l, p->l, a, b, akt_a, mid);
auto v2 = oblicz(k->r, p->r, a, b, mid + 1, akt_b);
return {v1.first + v2.first, v1.second + v2.second};
}
pair<ll,ll> obl(int k, int p, int a, int b){
//cout << p << " " << k << " przedzial\n";
//cout << a << " " << b << " wartosci\n";
return oblicz(roots[k], roots[p-1], a, b, 1, base);
}
int isans[MAXN];
vector<int> wlacz[MAXN];
vector<int> wylacz[MAXN];
array<int, 3> updejt[MAXN];
set<array<int, 3>> curr;
int koniec[MAXN];
bool czy(int pref, int suff, ll ile1, ll ile2, int n){
int pocz = pref;
int kon = n - suff + 1;
int v = iloscB(1, pocz + 1, kon - 1, 1, base);
if(ile1 > v) return false;
v = iloscB(1, 1, pocz, 1, base);
pref = ktaB(1, 1, base, 0, v + ile1 + 1) - 1;
v = iloscR(1, pocz + 1, kon - 1, 1, base);
if(ile2 > v) return false;
return true;
}
int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
cin >> n >> m;
M = n + 1;
int a, b;
cin >> s;
int p1 = 0;
int s1 = 0;
for(int i = 0; i < n; ++i){
if(s[i] == '>' or s[i] == 'R'){
p1++;
}
else{
break;
}
}
for(int i = n - 1; i >= 0; --i){
if(s[i] == '<' or s[i] == 'B'){
s1++;
}
else{
break;
}
}
//liczenie drzewa strzalek
{
for(int i = 0; i < n; ++i){
if(s[i] == '>' or s[i] == 'R'){
strzalki[i + base] = {1, 0};
}
else{
strzalki[i + base] = {0, 1};
}
}
for(int i = base - 1; i > 0; --i){
strzalki[i] = {strzalki[2 * i].sR + strzalki[2 * i + 1].sR, strzalki[2 * i].sB + strzalki[2 * i + 1].sB};
}
}
//liczenie 2 czesci
{
krasnoludki.push_back(-1);
for(int i = 0; i < m; ++i){
cin >> a;
krasnoludki.push_back(a);
drugaczesc[i + base].swapy = {{0, a - 1, a + 1}, {a, n, a}};
}
for(int i = m + base; i < 2 * base; ++i){
drugaczesc[i].swapy = {{0, n, 0}};
}
for(int i = base - 1; i > 0; --i){
//cout << i << " i\n";
auto v1 = drugaczesc[2 * i].swapy;
auto v2 = drugaczesc[2 * i + 1].swapy;
vector<c> odp;
auto policz = [&](int a, int b, int dod){
int p = 0;
int k = v2.size() - 1;
while(p != k){
int sr = (p + k) / 2;
if(v2[sr].b < a){
p = sr + 1;
}
else{
k = sr;
}
}
if(v2[p].a <= a and b <= v2[p].b){
//cout << (a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[p].dod << " if1\n";
odp.push_back({(a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[p].dod});
return;
}
//cout << a << " " << b << " ab\n";
int curr = p;
//cout << (a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " lewo\n";
odp.push_back({(a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
curr++;
while(v2[curr].a <= b){
if(v2[curr].b <= b){
//cout << (v2[curr].a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " mid\n";
odp.push_back({(v2[curr].a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
}
else{
//cout << (v2[curr].a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " prawo\n";
odp.push_back({(v2[curr].a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[curr].dod});
break;
}
if(curr == v2.size() - 1) break;
curr++;
}
return;
};
for(auto u : v1){
int valdod = (u.a + u.dod) % M;
int valkon = (u.b + u.dod) % M;
//cout << valdod << " " << valkon << " pk\n";
if(valdod <= valkon){
policz(valdod, valkon, u.dod);
}
else{
policz(valdod, n, u.dod);
policz(0, valkon, u.dod);
}
}
vector<c> tmp;
for(auto u : odp){
if(u.a > u.b){
tmp.push_back({0, u.b, u.dod});
tmp.push_back({u.a, n, u.dod});
}
else{
tmp.push_back(u);
}
tmp.back().dod %= M;
}
odp = tmp;
// for(auto u : odp){
// cout << u.a << " " << u.b << " " << u.dod << " po zlozeniu\n";
// }
sort(odp.begin(),odp.end(),comp);
drugaczesc[i].swapy = odp;
}
}
//liczenie trwalego drzewa ilosci elementu
roots[0] = build();
for(int i = 1; i <= m; ++i){
roots[i] = add(roots[i - 1], krasnoludki[i]);
//cout << roots[i]->ile << " " << roots[i]->suma << " " << i << " roots\n";
}
int q;
cin >> q;
for(int i = 0; i < q; ++i){
cin >> a >> b;
if(p1 + s1 == n){
ans[i] = drugiwyn(1, a, b, 1, base, p1);
}
else{
queries.push_back({p1, s1, i, a, b});
}
}
while(queries.size() > 0){
//cout << queries.size() << " sajz\n";
for(int i = 0; i < queries.size(); ++i){
//cout << queries[i].a << " " << queries[i].b << " ab\n";
wlacz[queries[i].a].push_back(i);
wylacz[queries[i].b].push_back(i);
isans[i] = 0;
updejt[i][2] = -1;
koniec[i] = -1;
}
for(int i = 1; i <= m; ++i){
for(auto u : wlacz[i]){
curr.insert({queries[u].pref + 1, n - queries[u].suff, u});
}
wlacz[i].clear();
while(curr.size() > 0){
//cout << (*curr.begin())[0] << " " << (*curr.begin())[1] << " pierw\n";
auto it = curr.upper_bound({krasnoludki[i] + 1, 0, 0});
if(it == curr.begin()) break;
--it;
if((*it)[0] > krasnoludki[i] or (*it)[1] < krasnoludki[i]) break;
//cout << "wej\n";
int nr = (*it)[2];
isans[nr] = 1;
updejt[nr][2] = krasnoludki[i];
updejt[nr][0] = obl(i - 1, queries[nr].a, 1, queries[nr].pref).second;
auto t = obl(i - 1, queries[nr].a, n - queries[nr].suff + 1, base);
updejt[nr][1] = (n * t.first - t.second);
//cout << i << " i\n";
koniec[nr] = i;
//cout << nr << " ustaw koniec\n";
curr.erase(it);
}
//cout << krasnoludki[i] << " dod\n";
for(auto u : wylacz[i]){
//cout << koniec[u] << " koniec\n";
if(isans[u] == 1) continue;
//cout << u << " nr\n";
//cout << "#\n";
updejt[u][2] = -1;
auto l = obl(i, queries[u].a, 1, queries[u].pref);
//cout << l.first << " " << l.second << " l\n";
updejt[u][0] = l.second;
auto t = obl(i, queries[u].a, n - queries[u].suff + 1, base);
updejt[u][1] = (n * t.first - t.second);
curr.erase({queries[u].pref + 1, n - queries[u].suff, u});
koniec[u] = queries[u].b;
}
wylacz[i].clear();
}
curr.clear();
//cout << "po\n";
for(int i = 0; i < queries.size(); ++i){
//cout << updejt[i][0] << " " << updejt[i][1] << " " << updejt[i][2] << " update\n";
pair<int,int> p = {queries[i].pref, queries[i].suff};
//cout << p.first << " " << p.second << " ps\n";
//cout << updejt[i][0] << " " << updejt[i][1] << " upd\n";
if(czy(p.first, p.second, updejt[i][0], updejt[i][1], n) == false){
//cout << "#\n";
pair<int,int> tmp;
if(krasnoludki[queries[i].a] <= p.first){
tmp = dodajp(p.first, p.second, krasnoludki[queries[i].a], n);
}
else{
tmp = dodajk(p.first, p.second, n - krasnoludki[queries[i].a], n);
}
if(tmp.first + tmp.second == n){
ans[queries[i].org] = drugiwyn(1, queries[i].a + 1, queries[i].b, 1, base, tmp.first);
continue;
}
int pocz = queries[i].a;
int kon = koniec[i];
while(pocz != kon){
int sr = (pocz + kon + 1) / 2;
auto pr = obl(sr, queries[i].a, 1, p.first);
auto su = obl(sr, queries[i].a, n - p.second + 1, base);
if(czy(p.first, p.second, pr.second, n * su.first - su.second, n)){
pocz = sr;
}
else{
kon = sr - 1;
}
}
auto pu = obl(pocz, queries[i].a, 1, p.first);
auto su = obl(pocz, queries[i].a, n - p.second + 1, base);
p = dodajp(p.first, p.second, pu.second, n);
p = dodajk(p.first, p.second, n * su.first - su.second, n);
if(krasnoludki[pocz + 1] <= p.first){
p = dodajp(p.first, p.second, krasnoludki[pocz + 1], n);
}
else{
p = dodajk(p.first, p.second, n - krasnoludki[pocz + 1], n);
}
ans[queries[i].org] = drugiwyn(1, pocz + 2, queries[i].b, 1, base, p.first);
continue;
}
if(updejt[i][2] == -1){
p = dodajp(p.first, p.second, updejt[i][0], n);
//cout << p.first << " " << p.second << " po pocz\n";
//cout << updejt[i][1] << " u1\n";
p = dodajk(p.first, p.second, updejt[i][1], n);
//cout << p.first << " " << p.second << " po obu\n";
if(p.first + p.second == n){
ans[queries[i].org] = p.first;
}
else{
int pocz = p.first;
int kon = n - p.second + 1;
ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base);
}
}
else{
p = dodajp(p.first, p.second, updejt[i][0], n);
//cout << p.first << " " << p.second << " po pocz\n";
p = dodajk(p.first, p.second, updejt[i][1], n);
//cout << p.first << " " << p.second << " po kon\n";
if(updejt[i][2] <= p.first){
p = dodajp(p.first, p.second, updejt[i][2], n);
}
else if(updejt[i][2] > n - p.second){
p = dodajk(p.first, p.second, n - updejt[i][2], n);
}
else{
p = dodajs(p.first, p.second, updejt[i][2], n);
}
//cout << p.first << " " << p.second << " po mid\n";
if(koniec[i] == queries[i].b){
if(p.first + p.second == n){
ans[queries[i].org] = p.first;
}
else{
int pocz = p.first;
int kon = n - p.second + 1;
ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base);
}
}
else if(p.first + p.second == n){
ans[queries[i].org] = drugiwyn(1, koniec[i] + 1, queries[i].b, 1, base, p.first);
}
else{
//cout << p.first << " " << p.second << " po srodku\n";
nowe.push_back({p.first, p.second, queries[i].org, koniec[i] + 1, queries[i].b});
}
}
}
queries = nowe;
nowe.clear();
}
for(int i = 0; i < q; ++i){
cout << ans[i] << "\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |