fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // We'll compute the cycle decomposition of the original permutation p (1-indexed)
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t; 
  10.     cin >> t;
  11.     while(t--){
  12.         int n; 
  13.         cin >> n;
  14.         vector<int> p(n+1);
  15.         for (int i = 1; i <= n; i++){
  16.             cin >> p[i];
  17.         }
  18.         vector<int> d(n+1);
  19.         for (int i = 1; i <= n; i++){
  20.             cin >> d[i];
  21.         }
  22.  
  23.         // --- Step 1. Compute cycle decomposition of p.
  24.         // cycleId[i] = the id (1-indexed) of the cycle to which index i belongs.
  25.         // cycleSize[id-1] will store the size of that cycle.
  26.         vector<int> cycleId(n+1, 0);
  27.         vector<int> cycleSize;
  28.         int cid = 0;
  29.         vector<bool> visited(n+1, false);
  30.         for (int i = 1; i <= n; i++){
  31.             if(!visited[i]){
  32.                 cid++;
  33.                 int cur = i;
  34.                 int cnt = 0;
  35.                 while(!visited[cur]){
  36.                     visited[cur] = true;
  37.                     cycleId[cur] = cid;
  38.                     cnt++;
  39.                     cur = p[cur];
  40.                 }
  41.                 cycleSize.push_back(cnt);
  42.             }
  43.         }
  44.  
  45.         // --- Step 2. Reverse simulation.
  46.         // In the forward process we “remove” entries one by one.
  47.         // In the reverse process we start with an all-zero array and “restore” entries in the reverse order.
  48.         // In the final fixed array (the original permutation) the cost (i.e. minimal operations needed)
  49.         // is 0. In the reverse simulation, if we have restored k indices then:
  50.         //     cost = (n - k) + (for each cycle C: if (restored in C) < |C| then (restored in C) else 0).
  51.         //
  52.         // Let F[k] be the cost when exactly k indices are restored.
  53.  
  54.         vector<long long> F(n+1, 0);
  55.         int activeCount = 0; // number of restored indices
  56.         long long currCost = n; // initially, no index is restored so cost = n (all indices missing)
  57.         F[0] = currCost;
  58.  
  59.         // For each cycle (by id) we track how many indices have been restored.
  60.         vector<int> cntCycle(cid+1, 0);
  61.  
  62.         // Process “adding back” indices in the reverse order of removals.
  63.         // d[1..n] gives the removal order; so we add in reverse: d[n], d[n-1], ..., d[1].
  64.         for (int i = 1; i <= n; i++){
  65.             int pos = d[n - i + 1]; // index we are restoring
  66.             activeCount++;
  67.             int cyc = cycleId[pos];
  68.  
  69.             // In cycle cyc, let old = (number restored before) and new = old+1.
  70.             int oldCount = cntCycle[cyc];
  71.             int newCount = oldCount + 1;
  72.  
  73.             // When we add one element:
  74.             //    (i) the missing count (n - activeCount) decreases by 1,
  75.             //    (ii) and the contribution for cycle cyc changes from:
  76.             //         prev = (oldCount if oldCount < cycleSize else 0)
  77.             //         to new  = (newCount if newCount < cycleSize else 0).
  78.             currCost -= 1; // decrease in missing count
  79.             int cycleTotal = cycleSize[cyc - 1];
  80.             int prevContribution = (oldCount < cycleTotal ? oldCount : 0);
  81.             int newContribution  = (newCount < cycleTotal ? newCount : 0);
  82.             currCost += (newContribution - prevContribution);
  83.  
  84.             cntCycle[cyc] = newCount;
  85.  
  86.             F[activeCount] = currCost;
  87.         }
  88.  
  89.         // --- Step 3. Answering queries.
  90.         // In the reverse simulation, F[k] is the answer (minimal operations needed)
  91.         // when k indices are restored. But note that if k indices are restored,
  92.         // then (n-k) indices were removed in the forward process.
  93.         // So for query i (i from 1 to n: i removals) the answer equals F[n-i].
  94.         vector<long long> ans(n+1, 0);
  95.         for (int i = 1; i <= n; i++){
  96.             int ac = n - i; // number of restored indices in the corresponding reverse state
  97.             ans[i] = F[ac];
  98.         }
  99.  
  100.         // Output the answer for the current test case.
  101.         // (We output n numbers: the i-th is the answer after i removals.)
  102.         for (int i = 1; i <= n; i++){
  103.             cout << ans[i] << (i==n ? "\n" : " ");
  104.         }
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
3
3
1 2 3
3 2 1
5
4 5 3 1 2
4 5 1 3 2
7
4 3 1 2 7 5 6
1 2 3 4 5 6 7
stdout
copy 
1 2 3
2 4 4 5 5
4 4 4 4 7 7 7
https://ideone.com/kKcDFM
language:
C++ (gcc 8.3)
created:
1 day 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!