Intro

Given a math expression with + or * sign with single digit numbers (1 to 9). Support the following operations:

Swap 2 number and evaluate the whole expression
flip an operator: from + to *, or from * to +
Flip all operators

Solution

Before we implement, pay attention to the problem statement that we have to print value modulo 1e9 + 7. So all add, subtract, and multiply will be done with modulo 1e9+7. No modulo will be explicitly stated in the following text.

We can observe that naively processing all queries will take \(O(NM)\) time, so we have to do some preprocessing. We can realize that * connects numbers through multiplication, and + divide the whole expression into several products and add them up. So I used a segtree to answer the query of product(i, j) to get the product of A[k] for k in [i, j). Now we have to support several operations:

Swapping 2 numbers: use binary search to find the corresponding product to both numbers. Subtract both from the overall result, and swap these 2 numbers, then add the 2 new products to the result.
Flip an operator: This can be divided into 2 cases. First case: the operator is '+', then we will minus the product to the left and to the right of this '+' sign, then remove this '+' sign and add the bigger product to the result.
Flip all operators: This can be done by setting up 2 sets for the index of add signs. Imagine we have 2 expression, the first is the original one, the second one is the one after flipping all operators. Then '+' signs in the second exp have same indexes as '*' sign in the first exp. By keeping track of 2 answers, then flip all operator is called, we can just output the other answer. We also maintain all other operators on both expressions (all cases covered above, no special case that needs extra work).

Code

Used a KACTL Segment Tree implementation with binary search on set in C++.

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int M = 1e9 + 7;

struct Tree {
	typedef ll T;
	static constexpr T unit = 1;
	T f(T a, T b) { return (a%M)*(b%M) % M; } // (any associative fn)
	vector<T> s; int n;
	Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vi v;
    set<int> add[2];
    ll ans[2]{};
    // add[0] is original
    // add[1] is all flipped
    add[0].insert(0);
    add[0].insert(n);
    add[1].insert(0);
    add[1].insert(n);
    for (int i = 0; i < 2*n-1; i++) {
        if (i%2 == 0) {
            v.push_back(s[i] - '0');
        } else {
            char c;
            c = s[i];
            if (c == '+') add[0].insert(i / 2 + 1);
            else add[1].insert(i / 2 + 1);
        }
    }
    Tree seg(n+1);
    rep(i, 0, n) {
        seg.update(i, v[i]);
        // cout << seg.query(i, i+1) << '\n';
    }
    // cout << seg.query(0, 1) << ' ' << seg.query(1, 3);
    rep(i, 0, 2) {
        for (auto it = next(add[i].begin()); it != add[i].end(); it++) {
            // cout << *prev(it) << ' ' << *it << '\n';
            ans[i] += seg.query(*prev(it), *it);
            ans[i] %= M;
        }
    }
    int cur = 0;
    cout << ans[cur] << '\n';
    rep(i, 0, m) {
        char c;
        cin >> c;
        if (c == 'a') {
            cur = 1 - cur;
        } else if (c == 's') {
            // swap 2 numbers
            int a, b;
            cin >> a >> b;
            a--; b--;
            rep(j, 0, 2) {
                if (j == 1) {
                    seg.update(a, v[a]);
                    seg.update(b, v[b]);
                }
                auto after = add[j].upper_bound(a);
                auto before = prev(after);
                ans[j] = (ans[j] + M - seg.query(*before, *after)) % M;
                after = add[j].upper_bound(b);
                before = prev(after);
                ans[j] = (ans[j] + M - seg.query(*before, *after)) % M;
                seg.update(b, v[a]);
                seg.update(a, v[b]);
                ans[j] = (ans[j] + seg.query(*before, *after)) % M;
                after = add[j].upper_bound(a);
                before = prev(after);
                ans[j] = (ans[j] + seg.query(*before, *after)) % M;
            }
            swap(v[a], v[b]);
        } else {
            // flip an operator
            int a;
            cin >> a;
            rep(j, 0, 2) {
                if (add[j].find(a) != add[j].end()) {
                    // has add here
                    auto it = add[j].find(a);
                    auto before = prev(it);
                    auto after = next(it);
                    ans[j] = (ans[j] + 2*M - seg.query(*before, *it) - seg.query(*it, *after)) % M;
                    ans[j] = (ans[j] + seg.query(*before, *after)) % M;
                    add[j].erase(a);
                } else {
                    // turn multiply into add
                    auto after = add[j].upper_bound(a);
                    ans[j] = (ans[j] + M - seg.query(*prev(after), *after)) % M;
                    ans[j] = (ans[j] + seg.query(*prev(after),a) + seg.query(a, *after)) % M;
                    add[j].insert(a);
                }
            }
        }
        cout << ans[cur] << '\n';
    }

    return 0;
}