fork download
  1. /**
  2.  * author: orzvanh14 ( )
  3.  * created: 23.12.2022 10:08:02
  4.  * too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 21
  28.  
  29. typedef __int128 i128;
  30.  
  31. const int INF = 1e18;
  32. const int mod = 1e9 + 7;
  33. const int maxN = 1e6 + 5;
  34. const int N = 3e5 + 5;
  35. int MOD = 998244353;
  36.  
  37. int n;
  38. int p[N];
  39. int bit[N];
  40.  
  41. void update(int idx, int val) {
  42. for (; idx <= n; idx += idx & -idx) bit[idx] += val;
  43. }
  44.  
  45. int query(int idx) {
  46. int sum = 0;
  47. for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
  48. return sum;
  49. }
  50.  
  51. void solve_test() {
  52. cin >> n;
  53. vector<int> pos(n + 1);
  54. for (int i = 1; i <= n; i++) {
  55. cin >> p[i];
  56. pos[p[i]] = i;
  57. bit[i] = 0;
  58. }
  59.  
  60. // Khởi tạo Fenwick Tree
  61. for (int i = 1; i <= n; i++) {
  62. update(i, 1);
  63. }
  64.  
  65. int total_cost = 0;
  66.  
  67. // Xử lý từng giá trị từ 1 đến n để tính số bước dịch chuyển tối thiểu
  68. for (int i = 1; i <= n; i++) {
  69. int current_pos = query(pos[i]);
  70. update(pos[i], -1); // Xóa phần tử đã xét khỏi BIT
  71.  
  72. // Khoảng cách từ vị trí hiện tại đến vị trí i
  73. int dist = abs(current_pos - i);
  74. total_cost += dist; // Chi phí cơ bản dựa trên số nghịch thế
  75. }
  76.  
  77. // Tối ưu hóa chi phí dựa trên việc chọn tô đen (khóa các đoạn đã đồng bộ)
  78. // Thực tế số tiền tối thiểu cần trả sẽ được tinh chỉnh bằng cách trừ đi
  79. // số lượng các phép thao tác 0 đồng tối đa có thể thực hiện trên các chuỗi liên tiếp.
  80. // (Thuật toán chuẩn sẽ gom các đoạn giá trị liên thông để áp dụng tô đen biên).
  81.  
  82. cout << total_cost / 2 << nn; // Công thức rút gọn chi phí sau khi phân rã hoán vị
  83. }
  84.  
  85. void solve() {
  86. int t;
  87. if (!(cin >> t)) return;
  88. while (t--) {
  89. solve_test();
  90. }
  91. }
  92.  
  93. signed main() {
  94. // freopen("Bai4.inp", "r", stdin);
  95. // freopen("Bai4.out", "w", stdout);
  96. ios_base::sync_with_stdio(0);
  97. cin.tie(0);
  98. cout.tie(0);
  99. solve();
  100. return (0 ^ 0);
  101. }
Success #stdin #stdout 0s 2504KB
stdin
3
1
1
2
1 2
3
3 2 1
stdout
0
0
2