fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. #define ll long long
  5. #define el cout << '\n'
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 2e5;
  10.  
  11. struct Segment_Tree
  12. {
  13.     int n;
  14.     vector<ll> tree, lazy;
  15.  
  16.     Segment_Tree(int n = 0) : n(n)
  17.     {
  18.         tree.assign(4 * maxn + 10, 0);
  19.         lazy.assign(4 * maxn + 10, 0);
  20.     };
  21.     void push(int id, int l, int r)
  22.     {
  23.         int m = l + r >> 1;
  24.         tree[id << 1] += (m - l + 1) * lazy[id];
  25.         tree[id << 1 | 1] += (r - m) * lazy[id];
  26.         lazy[id << 1] += lazy[id];
  27.         lazy[id << 1 | 1] += lazy[id];
  28.         lazy[id] = 0;
  29.     }
  30.     void update(int id, int l, int r, int u, int v, ll val)
  31.     {
  32.         if (r < u || l > v || u > v)
  33.             return ;
  34.         if (u <= l && r <= v)
  35.         {
  36.             tree[id] += val;
  37.             lazy[id] += val;
  38.             return ;
  39.         }
  40.         int m = l + r >> 1;
  41.         push(id, l, r);
  42.         update(id << 1, l, m, u, v, val);
  43.         update(id << 1 | 1, m + 1, r, u, v, val);
  44.         tree[id] = tree[id << 1] + tree[id << 1 | 1];
  45.     }
  46.     ll get(int id, int l, int r, int u, int v)
  47.     {
  48.         if (r < u || l > v || u > v)
  49.             return 0;
  50.         if (u <= l && r <= v)
  51.             return tree[id];
  52.         int m = l + r >> 1;
  53.         push(id, l, r);
  54.         return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
  55.     }
  56. } st_1, st_2;
  57.  
  58. int n, p[maxn + 10], q;
  59. ll res = 0, c[maxn + 10];
  60. vector<ll> v;
  61.  
  62. signed main()
  63. {
  64.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  65.     if (fopen("SAPXEP.INP", "r"))
  66.     {
  67.         freopen("SAPXEP.INP", "r", stdin);
  68.         freopen("SAPXEP.OUT", "w", stdout);
  69.     }
  70.  
  71.     cin >> n;
  72.     for (int i = 1; i <= n; i++)
  73.     {
  74.         cin >> p[i];
  75.         v.push_back(p[i]);
  76.     }
  77.     sort(v.begin(), v.end());
  78.     for (int i = 1; i <= n; i++)
  79.     {
  80.         p[i] = upper_bound(v.begin(), v.end(), p[i]) - v.begin();
  81.         int x = i;
  82.         int y = p[i];
  83.         if (x > y)
  84.             swap(x, y);
  85.         if (x == y)
  86.             continue;
  87.         st_2.update(1, 1, n, x, y - 1, 1);
  88. //        cout << x << ' ' << y, el;
  89.     }
  90.     for (int i = 1; i < n; i++)
  91.     {
  92.         int x = i;
  93.         int y = p[i];
  94.         if (x > y)
  95.             swap(x, y);
  96.         cin >> c[i];
  97.         st_1.update(1, 1, n, i, i, c[i]);
  98.         res += c[i] * st_2.get(1, 1, n, i, i);
  99.     }
  100.     cout << res, el;
  101.     cin >> q;
  102.     while (q--)
  103.     {
  104.         int t, x, y, a, b;
  105.         cin >> t >> x >> y;
  106.         a = x;
  107.         b = y;
  108.         if (t == 1)
  109.         {
  110.             int tmp_x = p[x];
  111.             int tmp_y = p[y];
  112.             if (tmp_x < x)
  113.                 swap(tmp_x, x);
  114.             if (tmp_y < y)
  115.                 swap(tmp_y, y);
  116. //            cout << x << ' ' << tmp_x << ' ' << y << ' ' << tmp_y, el;
  117.             res -= st_1.get(1, 1, n, x, tmp_x - 1);
  118.             res -= st_1.get(1, 1, n, y, tmp_y - 1);
  119.             st_2.update(1, 1, n, x, tmp_x - 1, -1);
  120.             st_2.update(1, 1, n, y, tmp_y - 1, - 1);
  121.             swap(p[a], p[b]);
  122.             tmp_x = p[a];
  123.             tmp_y = p[b];
  124.             if (tmp_x < a)
  125.                 swap(tmp_x, a);
  126.             if (tmp_y < b)
  127.                 swap(tmp_y, b);
  128. //            cout << a << ' ' << tmp_x << ' ' << b << ' ' << tmp_y, el;
  129.             res += st_1.get(1, 1, n, a, tmp_x - 1);
  130.             res += st_1.get(1, 1, n, b, tmp_y - 1);
  131.             st_2.update(1, 1, n, a, tmp_x - 1, 1);
  132.             st_2.update(1, 1, n, b, tmp_y - 1, 1);
  133.         }
  134.         else
  135.         {
  136.             res -= st_1.get(1, 1, n, x, x) * st_2.get(1, 1, n, x, x);
  137.             st_1.update(1, 1, n, x, x, y - c[x]);
  138.             res += st_1.get(1, 1, n, x, x) * st_2.get(1, 1, n, x, x);
  139.             c[x] = y;
  140.         }
  141.         cout << res, el;
  142.     }
  143. }
  144.  
Success #stdin #stdout 0.01s 28156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Bd6Ghn
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!