ICPC Domestic G: 数式探し

a * b + c * d * eみたいに+と*のみからなる式が与えられた時に，いろんな部分文字列を高速に評価するのが本質です。

こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが，SegTreeで強引にやってしまえばノード2個のマージに落とせるため，(SegTreeが思考停止で書けるという前提のもとでは)思考停止で掛けてそこまでバグりません

↓頑張ってコメントを足したコードです

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

//こういうのはenumを使ったほうがいいのかもしれません
const int PLUS = -1; 
const int MUL = -2;

const ll INF = TEN(9) + TEN(4);


// 数式の情報を表すノードです
struct D {
    // 数式の中に+が入っていないかのフラグです。これがtrueだと a * b * c * ... * z みたいに単一の項であることを表します    
    bool f = true;

    // この数式は l + m + rですよという値です。f = trueの場合mに値が入っていて，l, rは0です
    ll l = 0, m = 0, r = 0;
};


// 根性
D merge(D l, D r, int op) {
    D d;
    if (op == PLUS) {
        d.f = false;
        if (l.f && r.f) {
            d.l = l.m;
            d.r = r.m;
            d.m = 0;
        } else if (l.f) {
            d.l = l.m;
            d.m = min(INF, r.l + r.m);
            d.r = r.r;
        } else if (r.f) {
            d.l = l.l;
            d.m = min(INF, l.m + l.r);
            d.r = r.m;
        } else {
            d.l = l.l;
            d.m = min(INF, l.m + l.r + r.l + r.m);
            d.r = r.r;
        }
    } else {
        assert(op == MUL);
        d.f = l.f && r.f;
        if (l.f && r.f) {
            d.l = 0;
            d.m = min(INF, l.m * r.m);
            d.r = 0;
        } else if (l.f) {
            d.l = min(INF, l.m * r.l);
            d.m = r.m;
            d.r = r.r;            
        } else if (r.f) {
            d.l = l.l;
            d.m = l.m;
            d.r = min(INF, l.r * r.m);
        } else {
            // 両方単一項ではなくて，l * rとやる場合です。
            // l.l + l.m + l.r * r.l + r.m + r.r なので，l.m ~ r.mが圧縮できて以下のようになります
            d.l = l.l;
            d.m = min(INF, l.m + l.r * r.l + r.m);
            d.r = r.r;
        }
    }
    return d;
}


// SegTreeです，僕は定数倍が必要ないならポインタベースのほうが書きやすいと強硬に主張しています
// このSegTreeの要素数は数字の個数で，葉以外のノードがそれぞれopを持っています
struct Node {
    using NP = Node*;
    NP l, r; int sz;
    D d; // そのノードの数式の値
    int op; // 葉以外が持っていて，PLUSかMULです

    Node(int _sz, const V<ll> &v, int off = 0) : sz(_sz) {
        if (sz == 1) {
            assert(v[off] > 0);
            d = D{true, 0, v[off], 0};
            return;
        }
        int lsz = sz/2;
        l = new Node(lsz, v, off);
        r = new Node(sz-lsz, v, off + 2*lsz);
        op = v[off + 2*lsz-1];//
        assert(op == MUL || op == PLUS);
        d = merge(l->d, r->d, op);
    }

    // a番目の数字からb-1番目の数字までの数式を取り出して，評価します
    D get(int a, int b) {
        // 単位元が無いので単位元がないタイプのsegtreeを書きましょう
        if (b <= 0 || sz <= a) assert(false);
        if (a <= 0 && sz <= b) return d;
        if (b <= sz/2) return l->get(a, b);
        if (sz/2 <= a) return r->get(a-sz/2, b-sz/2);
        D ld = l->get(a, b);
        D rd = r->get(a-sz/2, b-sz/2);
        return merge(ld, rd, op);
    }
};


ll n;
string s;
int p;

ll ans; // グローバル変数で，答えはここにどんどん足しこまれていきます


// vは{数字, op, 数字, op, 数字, op, 数字, ..., 数字}みたいになっています
// 副作用として答えをansに足しこんで，最後に数式全体を評価した値を返します
ll solve2(V<ll> v) {
    assert(v.size() % 2);
    int m = int(v.size()) / 2 + 1; // 数字の個数
    auto tr = new Node(m, v);

    //a番目の数字からb-1番目の数字を評価して返す
    auto eval = [&](int a, int b) {
        auto d = tr->get(a, b);
        return min(INF, d.l + d.m + d.r);
    };
    for (int i = 0; i < m; i++) {
        int l, r, a, b;
        l = i, r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) < n) {
                l = md;
            } else {
                r = md;
            }
        }
        a = r;
        l = i; r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) <= n) {
                l = md;
            } else {
                r = md;
            }
        }
        b = r;
        ans += b-a;
    }
    return eval(0, m);
}

// 数式全体を評価した値を返します，最後に呼んでいるsolve2(v)の内側でansに答えが足し込まれます
ll solve() {
    V<ll> v;
    while (p != int(s.size()) && s[p] != ')') {
        char c = s[p];
        if (c == '(') {
            p++;
            v.push_back(solve());
            assert(s[p] == ')'); p++;
            continue;
        }
        if (isdigit(c)) {
            p++;
            v.push_back(c - '0');
            continue;
        }
        if (c == '*') {
            p++;
            v.push_back(MUL);
            continue;
        }
        if (c == '+') {
            p++;
            v.push_back(PLUS);
            continue;
        }
        assert(false);
    }
    return solve2(v);
}

bool first() {
    cin >> n;
    if (!n) return false;
    cin >> s; p = 0;

    ans = 0;
    solve();
    cout << ans << endl;
    return true;
}

int main() {
    while (first()) {}
}