Advertisement
Vince14

/<> 7578 (top down seg tree)

Sep 21st, 2023
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<long long, long long>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 500005;
  23.  
  24. int N, arr[MAXN], comp[MAXN * 2], loc[MAXN], seg[MAXN * 4];
  25. long long ans = 0;
  26.  
  27. void update(int x, int s, int e, int idx, int val){
  28.     if(idx < s or idx > e) return;
  29.     if(s == e){
  30.         seg[x] = val;
  31.         return;
  32.     }
  33.  
  34.     int mid = (s + e)/2;
  35.     update(x * 2, s, mid, idx, val);
  36.     update(x * 2 + 1, mid + 1, e, idx, val);
  37.     seg[x] = seg[x * 2] + seg[x * 2 + 1];
  38. }
  39.  
  40. int query(int x, int s, int e, int a, int b){
  41.     if(b < s or a > e) return 0;
  42.     if(a <= s and e <= b) return seg[x];
  43.  
  44.     int mid = (s + e)/2;
  45.     return query(x * 2, s, mid, a, b) + query(x * 2 + 1, mid + 1, e, a, b);
  46. }
  47.  
  48. int main() {
  49.     FAST;
  50.     cin >> N;
  51.     for(int x, i = 1; i <= N; i++){
  52.         cin >> x;
  53.         comp[x] = i;
  54.     }
  55.     for(int x, i = 1; i <= N; i++){
  56.         cin >> x;
  57.         arr[i] = comp[x];
  58.         loc[arr[i]] = i;
  59.     }
  60.     for(int i = 1; i <= N; i++){
  61.         int add = loc[i] - 1 - query(1, 1, N, 1, loc[i] - 1);
  62.         // cout << i << " " << add << "\n";
  63.         ans += add;
  64.         update(1, 1, N, loc[i], 1);
  65.     }
  66.     cout << ans << "\n";
  67. }
  68.  
  69. /*
  70. 5
  71. 132 392 311 351 231
  72. 392 351 132 311 231
  73.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement