fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // make sure modify 0LL + , 1LL * , overflow when remove define
  6. #define int long long
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. struct BIT {
  10.     int n;
  11.     vector<int> tree;
  12.  
  13.     void init(int _n) {
  14.         n = _n, tree.assign(_n, 0);
  15.     }
  16.  
  17.     void add(int at, int value) {
  18.         for (int i = at + 1; i <= n; i += i & -i)
  19.             tree[i - 1] += value;
  20.     }
  21.  
  22.     int sum(int exc) {
  23.         int ans = 0;
  24.         for (int i = exc; i > 0; i -= i & -i)
  25.             ans += tree[i - 1];
  26.         return ans;
  27.     }
  28.  
  29.     int sum(int inc, int exc) {
  30.         return sum(exc) - sum(inc);
  31.     }
  32.  
  33.     int search(int value) {
  34.         int sum = 0, pos = -1;
  35.         // decrease
  36.         for (int i = 25; i >= 0; --i) {
  37.             if (pos + (1 << i) < n and sum + tree[pos + (1 << i)] < value)
  38.                 sum += tree[pos + (1 << i)], pos += (1 << i);
  39.         }
  40.         // pos : less than val
  41.         return pos + 1;
  42.     }
  43. };
  44.  
  45. vector<vector<int>> adj;
  46.  
  47. int ct = 0;
  48. vector<bool> vis;
  49. vector<int> in, out;
  50. void dfs(int u) {
  51.     vis[u] = true;
  52.     in[u] = ct++;
  53.     for (int ch : adj[u])
  54.         dfs(ch);
  55.     out[u] = ct;
  56. }
  57.  
  58. void get_shit_done() {
  59.     int n, q;
  60.     cin >> n >> q;
  61.  
  62.     string s;
  63.     cin >> s;
  64.  
  65.     vector<int> a(2 * n);
  66.     for (int i = 0; i < 2 * n; ++i)
  67.         cin >> a[i];
  68.  
  69.     adj.assign(2 * n, {});
  70.     vector<int> close(2 * n), t;
  71.     for (int i = 0; i < 2 * n; ++i) {
  72.         if (s[i] == '(') {
  73.             if ( not t.empty() )
  74.                 adj[t.back()].push_back(i);
  75.             t.push_back(i);
  76.         } else {
  77.             close[t.back()] = i;
  78.             t.pop_back();
  79.         }
  80.     }
  81.  
  82.     BIT tree;
  83.     tree.init(2 * n + 1);
  84.  
  85.     ct = 0;
  86.     in.assign(2 * n, 0);
  87.     out.assign(2 * n, 0);
  88.     vis.assign(2 * n, false);
  89.     for (int i = 0; i < 2 * n; ++i) {
  90.         if (not vis[i] and s[i] == '(')
  91.             dfs(i);
  92.     }
  93.  
  94.     while (q--) {
  95.         int op;
  96.         cin >> op;
  97.         if (op == 1) {
  98.             int l1, r1, l2, r2, x;
  99.             cin >> l1 >> r1 >> l2 >> r2 >> x;
  100.             --l1, --r1, --l2, --r2;
  101.             if (l1 > l2) {
  102.                 swap(l1, l2);
  103.                 swap(r1, r2);
  104.             }
  105.             if ( l2 < r1 )
  106.                 tree.add(in[l1], x);
  107.             else
  108.                 tree.add(in[l2], x);
  109.         } else {
  110.             int l, r;
  111.             cin >> l >> r;
  112.             --l, --r;
  113.             cout << a[l] + tree.sum(in[l], out[l]) << '\n';
  114.         }
  115.     }
  116. }
  117.  
  118. signed main() {
  119.     _3bkarm
  120.  
  121.     int ts = 1;
  122.     cin >> ts;
  123.     while (ts--) {
  124.         get_shit_done();
  125.     }
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dwXLX2
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!