#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 d2{
int ileakt;
int ilenieakt;
int sumaakt;
int sumanieakt;
int minimalny;
};
d2 drzew[2 * base];
vector<int> wylacz[MAXN];
const int INF = 1e9;
void cofnij(){
for(int i = 1; i <= m; ++i){
drzew[i + base - 1] = {1, 0, n - krasnoludki[i], 0, krasnoludki[i]};
}
for(int i = base + m; i < 2 * base; ++i){
drzew[i] = {0, 0, 0, 0, INF};
}
for(int i = base - 1; i > 0; --i){
drzew[i].ileakt = drzew[2 * i].ileakt + drzew[2 * i + 1].ileakt;
drzew[i].ilenieakt = drzew[2 * i].ilenieakt + drzew[2 * i + 1].ilenieakt;
drzew[i].sumaakt = drzew[2 * i].sumaakt + drzew[2 * i + 1].sumaakt;
drzew[i].sumanieakt = drzew[2 * i].sumanieakt + drzew[2 * i + 1].sumanieakt;
drzew[i].minimalny = min(drzew[2 * i].minimalny, drzew[2 * i + 1].minimalny);
}
return;
}
bool comp2(const zap &z1, const zap &z2){
if(z1.pref != z2.pref){
return z1.pref < z2.pref;
}
return false;
}
void akt(int w){
w += base - 1;
drzew[w] = {0, 1, 0, krasnoludki[w - base + 1], INF};
w /= 2;
while(w != 0){
drzew[w].ileakt = drzew[2 * w].ileakt + drzew[2 * w + 1].ileakt;
drzew[w].ilenieakt = drzew[2 * w].ilenieakt + drzew[2 * w + 1].ilenieakt;
drzew[w].sumaakt = drzew[2 * w].sumaakt + drzew[2 * w + 1].sumaakt;
drzew[w].sumanieakt = drzew[2 * w].sumanieakt + drzew[2 * w + 1].sumanieakt;
drzew[w].minimalny = min(drzew[2 * w].minimalny, drzew[2 * w + 1].minimalny);
w /= 2;
}
return;
}
int znajdz(int w, int akt_a, int akt_b, int granica){
if(akt_a == akt_b) return akt_a;
int mid = (akt_a + akt_b) / 2;
//cout << w << " " << drzew[2 * w].minimalny << " " << drzew[2 * w + 1].minimalny << " d\n";
//cout << granica << " granica\n";
if(drzew[2 * w].minimalny < granica){
return znajdz(2 * w, akt_a, mid, granica);
}
else{
return znajdz(2 * w + 1, mid + 1, akt_b, granica);
}
return -1;
}
int znajdzsrodek(int w, int a, int b, int akt_a, int akt_b, int granica){
//cout << w << " " << a << " " << b << " " << akt_a << " " << akt_b << " " << granica << " drzewo\n";
if(a <= akt_a and akt_b <= b){
//cout << w << " " << drzew[w].minimalny << " " << granica << " oblsr\n";
//cout << "#\n";
//cout << drzew[w].minimalny << " " << granica << " gr\n";
if(drzew[w].minimalny >= granica) return -1;
else return znajdz(w, akt_a, akt_b, granica);
}
if(akt_a > b or akt_b < a) return -1;
int mid = (akt_a + akt_b) / 2;
int v1 = znajdzsrodek(2 * w, a, b, akt_a, mid, granica);
if(v1 != -1) return v1;
else return znajdzsrodek(2 * w + 1, a, b, mid + 1, akt_b, granica);
}
struct trzy{
int pref;
int suff;
int ind;
};
trzy szuk;
bool czy(int pref, int suff, int ile1, int ile2){
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 ostatni(int w, int akt_a, int akt_b, int aktpref, int aktsuff){
if(akt_a == akt_b) {
szuk.pref += drzew[w].sumanieakt;
szuk.suff += drzew[w].sumaakt;
return akt_a;
}
int mid = (akt_a + akt_b) / 2;
if(czy(aktpref, aktsuff, szuk.pref + drzew[2 * w].sumanieakt, szuk.suff + drzew[2 * w + 1].sumaakt)){
szuk.pref += drzew[2 * w].sumanieakt;
szuk.suff += drzew[2 * w].sumaakt;
return ostatni(2 * w + 1, mid + 1, akt_b, aktpref, aktsuff);
}
else{
return ostatni(2 * w, akt_a, mid, aktpref, aktsuff);
}
}
int znajdzostatni(int w, int a, int b, int akt_a, int akt_b, int aktpref, int aktsuff){
if(a > b){
szuk = {0, 0, b};
return b;
}
if(a <= akt_a and akt_b <= b){
if(czy(aktpref, aktsuff, szuk.pref + drzew[w].sumanieakt, szuk.suff + drzew[w].sumaakt) == true){
szuk.pref += drzew[w].sumanieakt;
szuk.suff += drzew[w].sumaakt;
return -1;
}
else{
int t = ostatni(w, akt_a, akt_b, aktpref, aktsuff);
szuk.ind = t;
return t;
}
}
if(akt_a > b or akt_b < a) return -1;
int mid = (akt_a + akt_b) / 2;
auto v1 = znajdzostatni(2 * w, a, b, akt_a, mid, aktpref, aktsuff);
if(v1 != -1) return v1;
auto v2 = znajdzostatni(2 * w + 1, a, b, mid + 1, akt_b, aktpref, aktsuff);
return v2;
}
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;
}
}
for(int i = 1; i <= m; ++i){
wylacz[krasnoludki[i]].push_back(i);
}
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});
}
}
cofnij();
while(queries.size() > 0){
sort(queries.begin(),queries.end(), comp2);
// for(auto u : queries){
// cout << u.pref << " " << u.suff << " zapytanie\n";
// }
int it = 0;
for(int i = 0; i <= n; ++i){
for(auto u : wylacz[i]){
//cout << u << " " << krasnoludki[u] << " wylaczyc\n";
akt(u);
}
while(it < queries.size() and queries[it].pref == i){
// for(int i = 1; i < 2 * base; ++i){
// cout << i << " " << drzew[i].minimalny << " mi\n";
// }
//cout << queries[it].a << " " << queries[it].b << " przedzial\n";
int ktory = znajdzsrodek(1, queries[it].a, queries[it].b, 1, base, n - queries[it].suff + 1);
//cout << i << " " << queries[it].org << " nr\n";
//cout << ktory << " kt\n";
if(ktory == -1){
pair<int,int> tmp = {queries[it].pref, queries[it].suff};
if(krasnoludki[queries[it].a] <= tmp.first){
tmp = dodajp(tmp.first, tmp.second, krasnoludki[queries[it].a], n);
}
else{
tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[queries[it].a], n);
}
if(tmp.first + tmp.second == n){
ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, tmp.first);
}
else{
szuk = {0, 0, -1};
znajdzostatni(1, queries[it].a, queries[it].b, 1, base, queries[it].pref, queries[it].suff);
if(szuk.ind == -1) szuk.ind = queries[it].b;
trzy ile = szuk;
//cout << ile.ind << " il\n";
pair<int,int> p = {queries[it].pref, queries[it].suff};
if(ile.ind == queries[it].b){
p = dodajp(p.first, p.second, ile.pref, n);
p = dodajk(p.first, p.second, ile.suff, n);
int kon = n - p.second + 1;
ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base);
}
else{
p = dodajp(p.first, p.second, ile.pref, n);
p = dodajk(p.first, p.second, ile.suff, n);
ile.ind++;
if(krasnoludki[ile.ind] <= p.first){
p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
}
else{
p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
}
ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first);
}
}
}
else{
if(ktory == queries[it].a){
//cout << "#\n";
pair<int,int> p = {queries[it].pref, queries[it].suff};
p = dodajs(p.first, p.second, krasnoludki[queries[it].a], n);
if(queries[it].a == queries[it].b){
int kon = n - p.second + 1;
ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base);
}
else if(p.first + p.second == n){
ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, p.first);
}
else{
//cout << p.first << " " << p.second << " nowe\n";
nowe.push_back({p.first, p.second, queries[it].org, queries[it].a + 1, queries[it].b});
}
}
else{
pair<int,int> tmp = {queries[it].pref, queries[it].suff};
if(krasnoludki[queries[it].a] <= tmp.first){
tmp = dodajp(tmp.first, tmp.second, krasnoludki[queries[it].a], n);
}
else{
tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[queries[it].a], n);
}
if(tmp.first + tmp.second == n){
ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, tmp.first);
}
else{
szuk = {0, 0, -1};
znajdzostatni(1, queries[it].a, ktory - 1, 1, base, queries[it].pref, queries[it].suff);
if(szuk.ind == -1) szuk.ind = ktory - 1;
trzy ile = szuk;
pair<int,int> p = {queries[it].pref, queries[it].suff};
//cout << ile.pref << " " << ile.suff << " " << ile.ind << " ile\n";
if(ile.ind != ktory - 1){
p = dodajp(p.first, p.second, ile.pref, n);
p = dodajk(p.first, p.second, ile.suff, n);
ile.ind++;
if(krasnoludki[ile.ind] <= p.first){
p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
}
else{
p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
}
ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first);
}
else{
p = dodajp(p.first, p.second, ile.pref, n);
p = dodajk(p.first, p.second, ile.suff, n);
ile.ind++;
if(krasnoludki[ile.ind] <= p.first){
p = dodajp(p.first, p.second, krasnoludki[ile.ind], n);
}
else if(krasnoludki[ile.ind] > n - p.second){
p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n);
}
else{
p = dodajs(p.first, p.second, krasnoludki[ile.ind], n);
}
//cout << p.first << " " << p.second << " nowa\n";
if(ile.ind == queries[it].b){
int kon = n - p.second + 1;
ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base);
}
else if(p.first + p.second == n){
ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first);
}
else{
nowe.push_back({p.first, p.second, queries[it].org, ile.ind + 1, queries[it].b});
}
}
}
}
}
++it;
}
}
queries = nowe;
nowe.clear();
cofnij();
}
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... |