Аліна та гори#12241

Аліна та гори (Розбір)

Автор проблеми:	Псюк Юрій
Підготовлено:	Псюк Юрій та Андрій Холод
Розбір:	Псюк Юрій

Рішення

Будемо вирішувати офлайн окремо для кожної пари $А$ та $В$ . Використаємо метод $D & Q$ . Коли розглядатимемо усі запити, що лежать на відрізку від $t L$ до $tR$ , з цетром $m$ , то щоб порахувати відповідь для запита, що проходить через сердину, підрахуємо масив $d s$ , що буде підтримувати $g$ ( [ $s_{i}$ s_i , $s_{m}$ s_m], $A$ , $B$ ) для $t L$ $\leq$ $i$ $\leq$ $m$ ,а для $m + 1$ m+1 $\leq$ $i$ $\leq$ $tR$ буде тримати $g$ ( [ $s_{m + 1}$ s_{m+1} , $s_{R}$ s_R], $A$ , $B$ ). Залишилось додати $f$ від рядків, що проходять через центр.

Складність становить $O ((n + q) * l o g (n))$ \mathcal{O}((n+q)*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++