surajmateti

Untitled

Sep 25th, 2021
795
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int main(){
  6.     int t; cin>>t;
  7.     while(t--)
  8.     {
  9.     int n; cin>>n; int a[n+1]; for(int i=1;i<=n;i++) cin>>a[i];
  10.     vector<int>last(n+1,0);
  11.     map<int,int>mp;
  12.     for(int i=1;i<=n;i++) mp[a[i]] = i;
  13.     for(auto i:mp)
  14.     {
  15.         last[i.second] ++;
  16.     }
  17.     int x[n+1]; vector<int>sum(n+1,0);
  18.     x[1] = 0; sum[1] = last[1];
  19.     for(int i=2;i<=n;i++)
  20.     {
  21.          x[i] = sum[i-1];
  22.          sum[i] = sum[i-1] + last[i];
  23.     }
  24.     vector<int>first(n+1,0);
  25.     mp.clear();
  26.     for(int i=n;i>=1;i--) mp[a[i]] = i;
  27.     for(auto i:mp)
  28.     {
  29.         first[i.second] ++;
  30.     }
  31.     for(int i=1;i<=n;i++) sum[i] = 0;
  32.     int y[n+1]; y[n] = 0; sum[n] = first[n];
  33.     for(int i=n-1;i>=1;i--)
  34.     {
  35.         y[i] = sum[i+1];
  36.         sum[i] = sum[i+1] + first[i];
  37.     }
  38.     for(int i=1;i<=n;i++) cout<<abs(x[i] - y[i])<<' '; cout<<"\n";
  39.     }
  40.     return 0;
  41.     }
RAW Paste Data