Subtask 1: Với mọi substring có thể có kiểm tra (sử dụng Stack) xem có thỏa mãn điều kiện là dãy ngoặc đúng hay không.

Độ phức tạp: ~O(n^3)~.

Subtask 2:

Nhận xét là dãy ngoặc đúng có thể sử dụng Stack theo cả hai đầu cùng một lúc. Từ đó ta sử dụng kỹ thuật chia để trị và Hashing để tính.

Ví dụ: ~()(())~

Ta có thể tách thành ~()(~ và ~())~ rồi chạy Stack riêng trên hai xâu, xâu ~()(~ theo chiều từ phải đến trái, xâu ~())~ theo chiều từ trái đến phải. Dãy ngoặc là đúng khi hai stack ghép lại được dãy ngoặc đúng và đối xứng

Độ phức tạp: ~O(n \log^2n )~

Subtask 3:

Làm tương tự ý tưởng chia để trị và Hashing như Subtask 2.

Độ phức tạp: ~O(n \log^2n )~

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int BASE = 331;

int n, rival[300], pq[MAXN], top;
int CodeHashLeft[MAXN], CodeHashRight[MAXN];
string s;

bool Open(int i) {
    return (!(s[i] == ')' || s[i] == ']' || s[i] == '}' || s[i] == '>'));
}

bool Close(int i) {
    return (s[i] == ')' || s[i] == ']' || s[i] == '}' || s[i] == '>');
}

int dnc(int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;

    top = 0;
    int cntClose = 0;
    int res = 0;

    map<int, int> cntLeft;
    for (int i = l - 1; i <= r + 1; i++) CodeHashLeft[i] = 0;

    for (int i = mid; i >= l; --i) {
        if (Close(i)) ++cntClose;

        if (top >= 1 && Open(i) && s[i] == rival[s[pq[top]]]) {
            CodeHashLeft[i] = CodeHashLeft[pq[top] + 1];
            top--;
            --cntClose;
        }
        else {
            pq[++top] = i;
            CodeHashLeft[i] = (CodeHashLeft[i + 1] * BASE + rival[s[i]]) % MOD;
        }

        if (cntClose == 0) cntLeft[CodeHashLeft[i]]++;
    }

    top = 0;
    int cntOpen = 0;
    for (int i = l - 1; i <= r + 1; i++) CodeHashRight[i] = 0;

    for (int i = mid + 1; i <= r; i++) {
        if (Open(i)) ++cntOpen;

        if (top >= 1 && Close(i) && s[i] == rival[s[pq[top]]]) {
            CodeHashRight[i] = CodeHashRight[pq[top] - 1];
            top--;
            --cntOpen;
        }
        else {
            pq[++top] = i;
            CodeHashRight[i] = (CodeHashRight[i - 1] * BASE + s[i]) % MOD;
        }


        if (cntOpen == 0) res += cntLeft[CodeHashRight[i]];
    }

    return res + dnc(l, mid) + dnc(mid + 1, r);
}

void solve() {
    cin >> s;
    n = sz(s);
    s = " " + s;

    cout << dnc(1, n);
}

#define TASK "A"
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    rival['('] = ')';
    rival[')'] = '(';

    rival['['] = ']';
    rival[']'] = '[';

    rival['{'] = '}';
    rival['}'] = '{';

    rival['<'] = '>';
    rival['>'] = '<';

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612