Với 1 xâu x bất kì có độ dài n gồm các kí tự (, ) và ?, nếu tồn tại 1 cách thay thế các dấu '?' để tạo thành 1 dãy ngoặc đúng thì cách điền này luôn tạo thành 1 dãy ngoặc đúng:

• Gọi số ( ban đầu là filled_open, số ) ban đầu là filled_close.

• Vì xâu sau khi điền là dãy ngoặc đúng, số lượng dấu ( bằng số lượng dấu ) bằng n/2.

• Vậy số dấu ( còn lại cần điền là n/2 - filled_open, số dấu ) còn lại cần điền là n/2 - filled_close.

• Chúng ta sẽ điền n/2 - filled_open dấu ? đầu tiên trong xâu là dấu (, và điền các dấu ? còn lại là dấu ).

Như vây, nếu cách điền trên không tạo thành dãy ngoặc đúng thì cũng không có cách điền nào khác để tạo thành dãy ngoặc đúng.

Chúng ta giữ 1 lazy segtree để tính min prefixsum. Với lazy segtree, ta có thể kiểm tra là khi ta điền một số dấu ?, có cách nào để điền các dấu ? còn lại để tạo thành dãy ngoặc đúng hay không. Để thực hiện việc kiểm tra, với các dấu ? chưa điền, ta cứ tạm thời điền theo quy luật trên. Khi ta update một dấu ? thành dấu ( và dấu ), ta cần sửa lại cách điền tạm thời để đảm bảo quy luật trên. Ví dụ: xâu của chúng ta hiện tại là (???. Cách điền tạm thời của xâu này là (()). Bây giờ, ví dụ như ta update dấu ? đầu tiên là ), xâu của mình là ()??, và cách điền tạm thời cho xâu này là ()(). Ta có thể nhận thấy là ta chỉ cần update tối đa 2 vị trí trong cách điền tạm thời đối với mỗi truy vấn update.

Bây giờ ta sẽ backtrack. Với mỗi vị trí dấu ? từ trái sang phải, ta thử các kí tự ( và ). Chúng ta dùng lazy segtree để kiểm tra nếu ta điền kí tự hiện tại, có cách nào để điền các kí tự ? khác để tạo thành dãy ngoặc đúng hay không.`

Lưu ý là chúng ta phải dừng backtrack sớm nếu đã tìm được 10 cách điền các dấu ?.

Ngoài việc sử dụng lazy segtree, ta cũng có thể dùng sparse table để giải bài này. Cách cài đặt phức tạp hơn nhiều.

Code lazy segtree:

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

#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

#endif  // ATCODER_LAZYSEGTREE_HPP

using S = int;
using F = int;

S op(S l, S r)
{
 return min(l, r);
}

S e()
{
 return 0x3f3f3f3f;
}

S mapping(F l, S r)
{
 return l + r;
}

F composition(F l, F r)
{
 return l + r;
}

F id()
{
 return 0;
}

int main()
{
  cin.tie(0)->sync_with_stdio(0);

  int t; cin >> t;
  while (t--)
  {
  auto greedy = [](string s) {
    int filled_open = count(s.begin(), s.end(), '(');
    int filled_close = count(s.begin(), s.end(), ')');

    int n = s.size();

    if (n % 2 == 1) return 0;

    int remaining_open = n / 2 - filled_open;
    int remaining_close = n / 2 - filled_close;

    if (remaining_open < 0 || remaining_close < 0) return 0;

    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);

    for (int i = 0; i < n; i++) seg.set(i, 0);

    auto is_balanced = [&]() {
      assert(seg.prod(n - 1, n) == 0);
      return seg.prod(0, n) >= 0;
    };

    auto increment = [&](int index, int value) {
      seg.apply(index, n, value);
    };

    // I know deque is slow :(
    deque<int> open_indices, close_indices;

    {
      int counter = 0;
      string filled;

      for (int i = 0; i < n; i++)
      {
        char x = s[i];

        if (x == '?')
        {
          if (counter < remaining_open)
          {
            open_indices.push_back(i);
            increment(i, 1);
          }
          else
          {
            close_indices.push_back(i);
            increment(i, -1);
          }
          counter++;
        }
        else
        {
          if (x == '(') increment(i, 1);
          else increment(i, -1);
        }
      }
    }

    auto turn_open_to_close = [&](int index) {
      increment(index, -2);
    };

    auto turn_close_to_open = [&](int index) {
      increment(index, 2);
    };

    auto get = [&](int i) {
      auto value = 
        i == 0
        ? seg.prod(0, 1)
        : seg.prod(i, i + 1) - seg.prod(i - 1, i);
      if (value == 1) return '(';
      return ')';
    };

    int counter = 0;

    auto dfs = [&](auto dfs, int index) {
      if (index == n)
      {
        counter++;
        if (counter >= 10) return false;
        return true;
      }

      if (s[index] != '?')
      {
        if (!dfs(dfs, index + 1)) return false;
        return true;
      }

      // probe '('
      if (get(index) == '(')
      {
        int popped = open_indices.front();
        open_indices.pop_front();
        if (!dfs(dfs, index + 1)) return false;
        open_indices.push_front(popped);
      }

      // probe ')'
      if (get(index) == ')')
      {
        int popped = close_indices.front();
        close_indices.pop_front();
        if (!dfs(dfs, index + 1)) return false;
        close_indices.push_front(popped);
      }
      else if (!close_indices.empty())
      {
        int popped_open = open_indices.front();
        open_indices.pop_front();
        int popped_close = close_indices.front();
        close_indices.pop_front();
        open_indices.push_back(popped_close);
        turn_open_to_close(popped_open);
        turn_close_to_open(popped_close);

        if (is_balanced())
        {
          if (!dfs(dfs, index + 1)) return false;
        }

        turn_open_to_close(popped_close);
        turn_close_to_open(popped_open);
        open_indices.pop_back();
        close_indices.push_front(popped_close);
        open_indices.push_front(popped_open);
      }

      return true;
    };

    if (!is_balanced()) return 0;

    dfs(dfs, 0);

    return counter;
  };
  string s; cin >> s;
  cout << greedy(s) << "\n";
  }
}

Code sparse table:

#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;

/**
 * Author: Johan Sannemo, pajenegod
 * Date: 2015-02-06
 * License: CC0
 * Source: Folklore
 * Description: Range Minimum Queries on an array. Returns
 * min(V[a], V[a + 1], ... V[b - 1]) in constant time.
 * Usage:
 *  RMQ rmq(values);
 *  rmq.query(inclusive, exclusive);
 * Time: $O(|V| \log |V| + Q)$
 * Status: stress-tested
 */
#pragma once

template<class T>
struct RMQ {
 vector<vector<T>> jmp;
 RMQ(const vector<T>& V) : jmp(1, V) {
     for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
         jmp.emplace_back(sz(V) - pw * 2 + 1);
         rep(j,0,sz(jmp[k]))
             jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
     }
 }
 T query(int a, int b) {
     assert(a < b); // or return inf if a == b
     int dep = 31 - __builtin_clz(b - a);
     return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
 }
};

int main()
{
  cin.tie(0)->sync_with_stdio(0);

  int t;
  cin >> t;

  while (t--)
  {
    string s;
    cin >> s;

    int n = s.size();

    if (n % 2 == 1)
    {
      cout << "0\n";
      continue;
    }

    int open_count = count(s.begin(), s.end(), '(');
    int close_count = count(s.begin(), s.end(), ')');
    int remaining_open = n / 2 - open_count;
    int remaining_close = n / 2 - close_count;
    int question_mark_count = count(s.begin(), s.end(), '?');

    if (remaining_open < 0 || remaining_close < 0)
    {
      cout << "0\n";
      continue;
    }

    vector<int> fill_open_balance_factor(n), fill_close_balance_factor(n);

    {
      int balance_factor = 0;
      for (int i = 0; i < n; i++)
      {
        if (s[i] == '(' || s[i] == '?') balance_factor++;
        else balance_factor--;

        fill_open_balance_factor[i] = balance_factor;
      }
    }

    {
      int balance_factor = 0;
      for (int i = 0; i < n; i++)
      {
        if (s[i] == ')' || s[i] == '?') balance_factor--;
        else balance_factor++;

        fill_close_balance_factor[i] = balance_factor;
      }
    }

    RMQ<int> min_fill_open(fill_open_balance_factor), min_fill_close(fill_close_balance_factor);

    // now maintaining the ranges is gonna prove difficult

    vector<int> question_mark_positions(count(s.begin(), s.end(), '?'));

    {
      int counter = 0;
      for (int i = 0; i < n; i++)
      {
        if (s[i] != '?') continue;
        question_mark_positions[counter] = i;
        counter++;
      }
    }

    int balance_factor = 0;
    int counter = 0;
    int current_open_count = 0;
    int current_close_count = 0;
    int current_question_mark_count = 0;

    auto dfs = [&](auto dfs, int index) {
      if (index == n)
      {
        counter++;
        if (counter >= 10)
        {
          counter = 10;
          return true;
        }
        return false;
      }

      if (s[index] != '?')
      {
        if (s[index] == '(') balance_factor++, current_open_count++; else balance_factor--, current_close_count++;
        if (balance_factor >= 0 && dfs(dfs, index + 1)) return true;
        if (s[index] == '(') balance_factor--, current_open_count--; else balance_factor++, current_close_count--;
        return false;
      }

      current_question_mark_count++;

      auto handle_new_balance_factor = [&]() {
        int difference = -balance_factor;
        int sum = n - index - 1;
        if ((sum + difference) % 2 != 0) return false;
        int total_open_count = (sum + difference) / 2;
        int total_close_count = (sum - difference) / 2;

        if (total_open_count < 0 || total_close_count < 0) return false;

        int filled_open_count = open_count - current_open_count;
        int filled_close_count = close_count - current_close_count;

        int remaining_open_count = total_open_count - filled_open_count;
        int remaining_close_count = total_close_count - filled_close_count;
        int remaining_question_mark_count = question_mark_count - current_question_mark_count;

        if (remaining_open_count < 0 || remaining_close_count < 0) return false;

        auto query_fill_open = [&](int left, int right) {
          return min_fill_open.query(left, right + 1);
        };

        auto query_fill_close = [&](int left, int right) {
          return min_fill_close.query(left, right + 1);
        };

        auto get_min_range_1 = [&]() {
          return query_fill_open(index + 1, question_mark_positions[current_question_mark_count + remaining_open_count - 1]) - fill_open_balance_factor[index] + balance_factor;
        };
        auto get_min_range_2 = [&]() {
          return query_fill_close(question_mark_positions[current_question_mark_count + remaining_open_count - 1] + 1, n - 1)
            - fill_close_balance_factor[question_mark_positions[current_question_mark_count + remaining_open_count - 1]]
            + fill_open_balance_factor[question_mark_positions[current_question_mark_count + remaining_open_count - 1]] - fill_open_balance_factor[index]
            + balance_factor;
        };

        int min_balance_factor;

        if (remaining_open_count == 0 && remaining_close_count == 0)
          min_balance_factor = 0;
        else if (remaining_open_count == 0)
          min_balance_factor = get_min_range_2();
        else if (remaining_close_count == 0)
          min_balance_factor = get_min_range_1();
        else
          min_balance_factor = min(get_min_range_1(), get_min_range_2());

        if (min_balance_factor < 0) return false;
        if (balance_factor < 0) return false;

        return dfs(dfs, index + 1);
      };

      int old_balance_factor = balance_factor;

      // probe '('
      {
        balance_factor = old_balance_factor + 1;
        if (handle_new_balance_factor()) return true;
        balance_factor = old_balance_factor;
      }

      // probe ')'
      {
        balance_factor = old_balance_factor - 1;
        if (handle_new_balance_factor()) return true;
        balance_factor = old_balance_factor;
      }

      current_question_mark_count--;

      return false;
    };

    dfs(dfs, 0);

    cout << counter << "\n";
  }
}

Độ phức tạp: O(nlogn).