Advertisement
Guest User

Untitled

a guest
Nov 6th, 2022
2,135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. struct bit
  5. {
  6.     vector<int> a;
  7.     void resize(int n)
  8.     {
  9.         a = vector<int>(n + 1);
  10.     }
  11.     void update(int pos, int val)
  12.     {
  13.         int n = (int)a.size() - 1;
  14.         for (int i = pos; i <= n; i += i & (-i))
  15.         {
  16.             a[i] += val;
  17.         }
  18.     }
  19.     int query(int pos)
  20.     {
  21.         int ans = 0;
  22.         for (int i = pos; i; i -= i & (-i))
  23.         {
  24.             ans += a[i];
  25.         }
  26.         return ans;
  27.     }
  28.     int query(int st, int dr)
  29.     {
  30.         return query(dr) - query(st - 1);
  31.     }
  32. };
  33. int32_t main()
  34. {
  35.     cin.tie(nullptr)->ios_base::sync_with_stdio(false);
  36.     int q;
  37.     cin >> q;
  38.     while (q--)
  39.     {
  40.         int n;
  41.         string s;
  42.         cin >> n >> s;
  43.         s = '$' + s;
  44.         vector<int> pref(n + 1);
  45.         for (int i = 1; i <= n; ++i)
  46.         {
  47.             pref[i] = pref[i - 1] + (s[i] == ')' ? -1 : 1);
  48.         }
  49.         vector<int> dp(n + 2);
  50.         stack<int> paranteze;
  51.         for (int i = n; i >= 1; --i)
  52.         {
  53.             if (s[i] == '(')
  54.             {
  55.                 if (!paranteze.empty())
  56.                 {
  57.                     dp[i] = dp[paranteze.top() + 1];
  58.                     paranteze.pop();
  59.                 }
  60.             }
  61.             else
  62.             {
  63.                 dp[i] = dp[i + 1] + (n - i + 1);
  64.                 paranteze.push(i);
  65.             }
  66.         }
  67.         int ans = 0;
  68.         for (int i = 1; i <= n; ++i)
  69.         {
  70.             ans += dp[i];
  71.         }
  72.         map<int, int> norm;
  73.         vector<int> lesgo = pref;
  74.         sort(lesgo.begin(), lesgo.end());
  75.         int p = 1;
  76.         for (int i = 0; i <= n; ++i)
  77.         {
  78.             if (norm.find(lesgo[i]) == norm.end())
  79.             {
  80.                 norm[lesgo[i]] = p++;
  81.             }
  82.         }
  83.         for (int i = 0; i <= n; ++i)
  84.         {
  85.             lesgo[i] = norm[pref[i]];
  86.         }
  87.         p--;
  88.         bit tree;
  89.         tree.resize(p);
  90.         for (int i = 0; i <= n; ++i)
  91.         {
  92.             ans += tree.query(1, lesgo[i]) * pref[i];
  93.             tree.update(lesgo[i], 1);
  94.         }
  95.         tree.resize(p);
  96.         for (int i = n; i >= 0; --i)
  97.         {
  98.             ans += tree.query(lesgo[i], p) * -pref[i];
  99.             tree.update(lesgo[i], 1);
  100.         }
  101.         cout << ans << '\n';
  102.     }
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement