fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define MAX 200005
  6.  
  7. int a[MAX], SongNghi[MAX];
  8. int cost[MAX], diffArr[MAX], cntArr[MAX];
  9. int n;
  10. map<int,int> iniPos, afterPos;
  11.  
  12. ll iniCost;
  13.  
  14. // Segment tree arrays and lazy for cnt updates
  15. ll stCost[4 * MAX], stCnt[4 * MAX], stCC[4 * MAX], lazy[4 * MAX];
  16.  
  17. void build(int id, int l, int r) {
  18.     if (l == r) {
  19.         stCost[id] = cost[l];
  20.         stCnt[id]  = cntArr[l];
  21.         stCC[id]   = stCost[id] * stCnt[id];
  22.         lazy[id]   = 0;
  23.         return;
  24.     }
  25.  
  26.     int mid = (l + r) / 2;
  27.     build(id * 2,     l,     mid);
  28.     build(id * 2 + 1, mid + 1, r);
  29.  
  30.     stCost[id] = stCost[id * 2] + stCost[id * 2 + 1];
  31.     stCnt[id]  = stCnt[id * 2]  + stCnt[id * 2 + 1];
  32.     stCC[id]   = stCC[id * 2]   + stCC[id * 2 + 1];
  33.     lazy[id]   = 0;
  34. }
  35.  
  36. void fix(int id, int l, int r) {
  37.     if (lazy[id] == 0) return;
  38.  
  39.     ll v = lazy[id];
  40.     stCC[id]  += stCost[id] * v;
  41.     stCnt[id] += (r - l + 1) * v;
  42.  
  43.     if (l < r) {
  44.         lazy[id * 2]     += v;
  45.         lazy[id * 2 + 1] += v;
  46.     }
  47.  
  48.     lazy[id] = 0;
  49. }
  50.  
  51. void updateCnt(int id, int l, int r, int u, int v, int val) {
  52.     fix(id, l, r);
  53.     if (l > v || r < u) return;
  54.  
  55.     if (l >= u && r <= v) {
  56.         lazy[id] += val;
  57.         fix(id, l, r);
  58.         return;
  59.     }
  60.  
  61.     int mid = (l + r) / 2;
  62.     updateCnt(id * 2,     l,     mid, u, v, val);
  63.     updateCnt(id * 2 + 1, mid + 1, r,   u, v, val);
  64.  
  65.     stCost[id] = stCost[id * 2] + stCost[id * 2 + 1];
  66.     stCnt[id]  = stCnt[id * 2]  + stCnt[id * 2 + 1];
  67.     stCC[id]   = stCC[id * 2]   + stCC[id * 2 + 1];
  68. }
  69.  
  70. void updateCost(int id, int l, int r, int pos, int nw) {
  71.     fix(id, l, r);
  72.  
  73.     if (l == r) {
  74.         ll delta    = nw - stCost[id];
  75.         stCost[id] = nw;
  76.         stCC[id]  += stCnt[id] * delta;
  77.         return;
  78.     }
  79.  
  80.     int mid = (l + r) / 2;
  81.     if (pos <= mid) {
  82.         updateCost(id * 2,     l,     mid, pos, nw);
  83.     } else {
  84.         updateCost(id * 2 + 1, mid + 1, r,   pos, nw);
  85.     }
  86.  
  87.     fix(id * 2,     l,     mid);
  88.     fix(id * 2 + 1, mid + 1, r);
  89.  
  90.     stCost[id] = stCost[id * 2] + stCost[id * 2 + 1];
  91.     stCnt[id]  = stCnt[id * 2]  + stCnt[id * 2 + 1];
  92.     stCC[id]   = stCC[id * 2]   + stCC[id * 2 + 1];
  93. }
  94.  
  95. int main() {
  96.     ios::sync_with_stdio(false);
  97.     cin.tie(nullptr);
  98.  
  99.     cin >> n;
  100.  
  101.     for (int i = 1; i <= n; i++) {
  102.         cin >> a[i];
  103.         SongNghi[i] = a[i];
  104.     }
  105.  
  106.     for (int i = 1; i < n; i++) {
  107.         cin >> cost[i];
  108.     }
  109.  
  110.     sort(SongNghi + 1, SongNghi + n + 1);
  111.  
  112.     for (int i = 1; i <= n; i++) {
  113.         iniPos[a[i]]          = i;
  114.         afterPos[SongNghi[i]] = i;
  115.     }
  116.  
  117.     fill(diffArr, diffArr + n + 1, 0);
  118.     for (int i = 1; i <= n; i++) {
  119.         int p = iniPos[a[i]];
  120.         int q = afterPos[a[i]];
  121.         if (p < q) {
  122.             diffArr[p]++;
  123.             diffArr[q]--;
  124.         } else if (q < p) {
  125.             diffArr[q]++;
  126.             diffArr[p]--;
  127.         }
  128.     }
  129.  
  130.     cntArr[0] = 0;
  131.     for (int i = 1; i < n; i++) {
  132.         cntArr[i] = cntArr[i - 1] + diffArr[i];
  133.     }
  134.  
  135.     build(1, 1, n - 1);
  136.     cout << stCC[1] << "\n";
  137.  
  138.     int Q;
  139.     cin >> Q;
  140.     while (Q--) {
  141.         int type, l, r;
  142.         cin >> type >> l >> r;
  143.  
  144.         if (type == 1) {
  145.             int x = a[l], y = a[r];
  146.  
  147.             int pX = iniPos[x];
  148.             int qX = afterPos[x];
  149.             if (pX != qX) {
  150.                 updateCnt(1, 1, n - 1, min(pX, qX), max(pX, qX) - 1, -1);
  151.             }
  152.  
  153.             int pY = iniPos[y];
  154.             int qY = afterPos[y];
  155.             if (pY != qY) {
  156.                 updateCnt(1, 1, n - 1, min(pY, qY), max(pY, qY) - 1, -1);
  157.             }
  158.  
  159.             swap(iniPos[x], iniPos[y]);
  160.             swap(a[l], a[r]);
  161.  
  162.             pX = iniPos[x];
  163.             qX = afterPos[x];
  164.             if (pX != qX) {
  165.                 updateCnt(1, 1, n - 1, min(pX, qX), max(pX, qX) - 1,  1);
  166.             }
  167.  
  168.             pY = iniPos[y];
  169.             qY = afterPos[y];
  170.             if (pY != qY) {
  171.                 updateCnt(1, 1, n - 1, min(pY, qY), max(pY, qY) - 1,  1);
  172.             }
  173.  
  174.         } else {
  175.             int old = cost[l];
  176.             updateCost(1, 1, n - 1, l, r);
  177.             cost[l] = r;
  178.         }
  179.  
  180.         cout << stCC[1] << "\n";
  181.     }
  182.  
  183.     return 0;
  184. }
  185.  
Success #stdin #stdout 0.01s 13864KB
comments (?)
stdin 
3
1 3 2
1 2
2
2 2 3
1 2 3
stdout 
4
6
0
https://ideone.com/aEbjF4
language:
C++14 (gcc 8.3)
created:
21 hours 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!