Alina and the Mountains#12241
Sign in

Alina and the Mountains (Editorial)

Problem Author:

Yurii Psiuk

Prepared by:

Yurii Psiuk and Andrii Kholod

Editorial:

Yurii Psiuk

Solution

We will solve the problem offline separately for each pair and . We will use the (Divide and Conquer) method. When we process all queries that lie within the segment from to with center , to calculate the answer for a query that crosses the middle, we compute an array which maintains g([s_i, s_m], A, B) for tL \le i \le m, and for m+1 \le i \le tR, it maintains g([s_{m+1}, s_R], A, B). All that remains is to add the function for strings that pass through the center.

The overall complexity is \mathcal{O}((n+q) \times \log(n)).

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppl;

ll ans[300009], a[300009], n, prs[300009], prcnt[300009],
   ds[300009], mod, psdes[300009], stdes[300009], number1, number2;

bool is(ll x){
    return (x == number1 || x == number2);
}

void dcq(ll L, ll R, vector<ppl> C){
    if(L > R || C.size() == 0) return;
    if(L == R) {
        for(auto x : C) ans[x.second] = is(a[L]) * a[L];
        return;
    }

    ll m = (L + R) >> 1;
    ds[m] = is(a[m]) * a[m];
    prs[m] = is(a[m]) * a[m];
    prcnt[m] = is(a[m]);

    ll k = is(a[m]) + 1; ll s = ds[m]; ll ma = s;
    for(int i = m - 1; i >= L; i--){
        ds[i] = ds[i+1];
        if(is(a[i])){
            ds[i] = (ds[i] + psdes[k] * a[i] + s) % mod;
            ma = (ma + stdes[k-1] * a[i]) % mod;
            s = (s + psdes[k] * a[i]) % mod;
            k++;
        } else {
            k = 1; s = 0; ma = 0;
        }
        if(k == m - i + 2) {
            prcnt[i] = prcnt[i+1] + 1;
            prs[i] = (prs[i+1] + ma) % mod;
        } else {
            prcnt[i] = prcnt[i+1];
            prs[i] = prs[i+1];
        }
    }

    ds[m+1] = is(a[m+1]) * a[m+1];
    prs[m+1] = is(a[m+1]) * a[m+1];
    prcnt[m+1] = is(a[m+1]);
    k = is(a[m+1]) + 1; s = ds[m+1]; ma = s;

    for(int i = m + 2; i <= R; i++){
        ds[i] = ds[i-1];
        if(is(a[i])){
            ds[i] = (ds[i] + k * a[i] + s * 10) % mod;
            ma = (ma * 10 + a[i]) % mod;
            s = (s * 10 + a[i] * k) % mod;
            k++;
        } else {
            k = 1; s = 0; ma = 0;
        }
        if(k == i - m + 1) {
            prcnt[i] = prcnt[i-1] + 1;
            prs[i] = (prs[i-1] + ma) % mod;
        } else {
            prcnt[i] = prcnt[i-1];
            prs[i] = prs[i-1];
        }
    }

    vector<ppl> AL, AR;
    for(auto x : C) {
        if(x.first.second == m) ans[x.second] = ds[x.first.first];
        else if(x.first.first == m+1) ans[x.second] = ds[x.first.second];
        else if(x.first.second < m) AL.push_back(x);
        else if(x.first.first > m+1) AR.push_back(x);
        else {
            ans[x.second] = (ds[x.first.first] + ds[x.first.second] +
                (prs[x.first.second] * prcnt[x.first.first] +
                 prs[x.first.first] * psdes[prcnt[x.first.second]] % mod * 10)) % mod;
        }
    }

    dcq(L, m-1, AL);
    dcq(m+2, R, AR);
}

void solve(){
    mod = 998244353;
    stdes[0] = 1;
    for(int i = 1; i <= 3e5; i++) stdes[i] = stdes[i-1] * 10 % mod;
    for(int i = 1; i <= 3e5; i++) psdes[i] = (psdes[i-1] + stdes[i-1]) % mod;

    vector<ppl> z[11][11];

    string s;
    cin >> s;
    n = s.size();
    for(int i = 1; i <= n; i++) a[i] = s[i-1] - '0';

    ll q, L, R;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        ll A, B;
        cin >> L >> R >> A >> B;
        if(A > B) swap(A, B);
        z[A][B].push_back({{L, R}, i});
    }

    for(int A = 1; A <= 9; A++)
        for(int B = A; B <= 9; B++) {
            number1 = A;
            number2 = B;
            dcq(1, n, z[A][B]);
        }

    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}
C++