fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "test"
  5.  
  6. #define int long long
  7. #define fi first
  8. #define sc second
  9. #define ii pair <int, int>
  10.  
  11. #define rep(i,s,e) for (int i = (s), _e = (e); i <= _e; i++)
  12. #define reo(i,s,e) for (int i = (s), _e = (e); i >= _e; i--)
  13.  
  14. const int maxn = 2e5;
  15. const int mod = 1e9 + 7;
  16. const int inf = 1e9;
  17.  
  18. int n, q;
  19. int a[maxn + 5], c[maxn + 5];
  20. int ans = 0;
  21.  
  22. struct Segment_Tree
  23. {
  24.     int n;
  25.     vector<int> tree, lazy;
  26.  
  27.     Segment_Tree (int n = 0) : n(n)
  28.     {
  29.         tree.assign(4 * maxn + 5, 0);
  30.         lazy.assign(4 * maxn + 5, 0);
  31.     };
  32.     void push(int id, int l, int r)
  33.     {
  34.         int m = l + r >> 1;
  35.         tree[id << 1] += (m - l + 1) * lazy[id];
  36.         tree[id << 1 | 1] += (r - m) * lazy[id];
  37.         lazy[id << 1] += lazy[id];
  38.         lazy[id << 1 | 1] += lazy[id];
  39.         lazy[id] = 0;
  40.     }
  41.     void update(int id, int l, int r, int u, int v, int val)
  42.     {
  43.         if (r < u || l > v || u > v)
  44.             return ;
  45.         if (u <= l && r <= v)
  46.         {
  47.             tree[id] += val;
  48.             lazy[id] += val;
  49.             return ;
  50.         }
  51.         int m = l + r >> 1;
  52.         push(id, l, r);
  53.         update(id << 1, l, m, u, v, val);
  54.         update(id << 1 | 1, m + 1, r, u, v, val);
  55.         tree[id] = tree[id << 1] + tree[id << 1 | 1];
  56.     }
  57.     int get(int id, int l, int r, int u, int v)
  58.     {
  59.         if (r < u || l > v || u > v)
  60.             return 0;
  61.         if (u <= l && r <= v)
  62.             return tree[id];
  63.         int m = l + r >> 1;
  64.         push(id, l, r);
  65.         return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
  66.     }
  67. } st1, st2;
  68.  
  69. ii getLR (int i)
  70. {
  71.     int l = i, r = a[i];
  72.     if (l > r) swap(l, r);
  73.     return {l, r - 1};
  74. }
  75.  
  76. signed main ()
  77. {
  78.     cin.tie(0)->sync_with_stdio(false);
  79.     #ifndef ONLINE_JUDGE
  80.     freopen(TASK".inp","r",stdin);
  81.     freopen(TASK".out","w",stdout);
  82.     #endif
  83.  
  84.     cin >> n;
  85.     rep (i, 1, n) cin >> a[i];
  86.     rep (i, 1, n - 1) cin >> c[i];
  87.  
  88.     vector <int> vec;
  89.     rep (i, 1, n) vec.push_back(a[i]);
  90.     sort(vec.begin(), vec.end());
  91.     vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  92.  
  93.     rep (i, 1, n)
  94.     {
  95.         st1.update(1, 1, n, i, i, c[i]);
  96.  
  97.         a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
  98.  
  99.         int l, r; tie(l, r) = getLR(i);
  100.         st2.update(1, 1, n, l, r, 1);
  101.     }
  102.  
  103.     rep (i, 1, n) ans += c[i] * st2.get(1, 1, n, i, i);
  104.     cout << ans << '\n';
  105.  
  106.     cin >> q;
  107.     while (q--)
  108.     {
  109.         int t, u, v;
  110.         cin >> t >> u >> v;
  111.  
  112.         if (t == 1)
  113.         {
  114.             int lu, ru; tie(lu, ru) = getLR(u);
  115.             int lv, rv; tie(lv, rv) = getLR(v);
  116.  
  117.             st2.update(1, 1, n, lu, ru, -1);
  118.             st2.update(1, 1, n, lv, rv, -1);
  119.  
  120.             ans -= st1.get(1, 1, n, lu, ru);
  121.             ans -= st1.get(1, 1, n, lv, rv);
  122.  
  123.             swap(a[u], a[v]);
  124.             tie(lu, ru) = getLR(u), tie(lv, rv) = getLR(v);
  125.  
  126.             st2.update(1, 1, n, lu, ru, 1);
  127.             st2.update(1, 1, n, lv, rv, 1);
  128.  
  129.             ans += st1.get(1, 1, n, lu, ru);
  130.             ans += st1.get(1, 1, n, lv, rv);
  131.         }
  132.         else
  133.         {
  134.             ans -= st1.get(1, 1, n, u, u) * st2.get(1, 1, n, u, u);
  135.             st1.update(1, 1, n, u, u, v - c[u]);
  136.             ans += st1.get(1, 1, n, u, u) * st2.get(1, 1, n, u, u);
  137.             c[u] = v;
  138.         }
  139.  
  140.         cout << ans << '\n';
  141.     }
  142.  
  143.     return 0;
  144. }
  145.  
  146.  
  147.  
Success #stdin #stdout 0.02s 28120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8fLIOr
language:
C++14 (gcc 8.3)
created:
7 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!