68TLE求助

#include <bits/stdc++.h>
#define ll long long
using namespace std;

namespace ljh {
    #define debug(x) cerr << #x << ":" << x << endl
    int qpow(int x, int y, const int P) {
        if (!y) return 1;
        int s = qpow(x, y >> 1, P);
        return (ll) s * s % P * (y & 1 ? x : 1) % P;
    }
}
using namespace ljh;

const int MAXN = 2e5 + 10;

int tong[MAXN], t[MAXN];
ll cnt;

int n, m, P, a[MAXN];
char s[MAXN];
ll ans[MAXN];

struct node {
    int l, r, id;
} e[MAXN];

inline bool cmp(node x, node y) {
    if (t[x.l] != t[y.l]) return t[x.l] < t[y.l];
    if (x.l & 1) return x.r < y.r;
    return x.r > y.r;
}

void add(int x) {
    cnt -= (ll) (tong[a[x]] - 1) * tong[a[x]] / 2;
    ++tong[a[x]];
    cnt += (ll) (tong[a[x]] - 1) * tong[a[x]] / 2;
}
void del(int x) {
    cnt -= (ll) (tong[a[x]] - 1) * tong[a[x]] / 2;
    --tong[a[x]];
    cnt += (ll) (tong[a[x]] - 1) * tong[a[x]] / 2;
}

void init() {
    for (int i = 0; i < MAXN; ++i) t[i] = i / 420;
    vector<int> vis;
    vis.push_back(0);
    for (int i = n, Pow = 1; i; --i) {
        a[i] = (a[i + 1] + (ll) Pow * (s[i] - 48) % P) % P;
        Pow = (ll) Pow * 10 % P;
        vis.push_back(a[i]);
    }
    stable_sort(vis.begin(), vis.end());
    auto End = unique(vis.begin(), vis.end());
    for (int i = 1; i <= n + 1; ++i)
        a[i] = lower_bound(vis.begin(), End, a[i]) - vis.begin();
}

void solve() {
    for (int i = 1; i <= n; ++i) {
        a[i] = !((s[i] - 48) % P);
        ans[i] = ans[i - 1] + a[i] * i;
        a[i] += a[i - 1];
    }
    scanf("%d", &m);
    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d %d", &l, &r);
        printf("%lld\n", ans[r] - ans[l - 1] - (a[r] - a[l - 1]) * (l - 1));
    }
}

int main() {
    scanf("%d %s", &P, s + 1);
    n = strlen(s + 1);
    if (P == 2 || P == 5) {
        solve();
        return 0;
    }
    init();
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &e[i].l, &e[i].r);
        ++e[i].r;
        e[i].id = i;
    }
    stable_sort(e + 1, e + 1 + m, cmp);
    for (int i = 1, l = 1, r = 0; i <= m; ++i) {
        while (l < e[i].l) del(l++);
        while (l > e[i].l) add(--l);
        while (r > e[i].r) del(r--);
        while (r < e[i].r) add(++r);
        ans[e[i].id] = cnt;
    }

    for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
    getchar();
    getchar();
    return 0;
}