Dsxv

top_speed

Jan 14th, 2020
264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std ;
  5. using namespace __gnu_pbds ;
  6.  
  7. #define int long long
  8.  
  9. typedef tree<int, null_type , less<int> , rb_tree_tag,
  10.             tree_order_statistics_node_update>
  11.         ordered_set  ;  
  12.  
  13. const int N = 2e5 + 10 ;
  14.  
  15. int t[4*N] ;
  16.  
  17. void build(int* a , int v , int tl , int tr){
  18.     if(tl == tr){
  19.         t[v] = a[tl] ;
  20.     }else{
  21.         int tm = (tl+tr)/2 ;
  22.         build(a, 2*v, tl, tm) ; build(a, 2*v+1, tm+1, tr) ;
  23.         t[v] = max(t[2*v], t[2*v+1]) ;
  24.     }
  25. }
  26.  
  27. int query(int v , int tl , int tr , int l , int r){
  28.     if(l > r){
  29.         return 0 ;
  30.     }
  31.     if(tl == l && tr == r){
  32.         return t[v] ;
  33.     }
  34.     int tm = (tl + tr) / 2 ;
  35.     return max(query(2*v, tl, tm, l, min(r,tm))
  36.         , query(2*v + 1, tm + 1, tr, max(l,tm+1), r) ) ;
  37. }
  38.  
  39. void update(int v , int tl , int tr , int pos , int new_val){
  40.     if(tl == tr){
  41.         t[v] = new_val ;
  42.     }else{
  43.         int tm = (tl + tr) / 2 ;
  44.         if(pos <= tm) // left jao
  45.             update(2*v, tl, tm, pos, new_val) ;
  46.         else
  47.             update(2*v + 1, tm+1, tr, pos, new_val) ;
  48.         t[v] = max(t[2*v] , t[2*v + 1]);
  49.     }
  50. }
  51.  
  52.  
  53. int32_t main(){
  54.     int tc ;
  55.     cin >> tc ;
  56.     while(tc--){
  57.         ordered_set s ;
  58.         for(int i = 0 ; i < 4*N ; i++) t[i] = 0 ;
  59.         int n ;
  60.         cin >> n ;
  61.         int a[n] ;
  62.         for(int i = 0 ; i < n ; i++) {
  63.             cin >> a[i] ;
  64.             s.insert(a[i]) ;
  65.         }
  66.         for(int i = 0 ; i < n ; i++) a[i] = s.order_of_key(a[i]) ;
  67.         build(a,1,0,n-1) ; // segtree from 1 index
  68.         vector<int> ans(n) ;
  69.         for(int i = n-1 ; i >= 0 ; i--) {
  70.             int ind = query(1,0,n-1,a[i],a[i]) ;
  71.             update(1,0,n-1,a[i],max(ind,i)) ;
  72.             ans[i] = max(0LL,query(1,0,n-1,0,a[i]-1) - i) ;
  73.         }
  74.         for(auto  i : ans) cout << i << " " ;
  75.         cout << endl ;
  76.     }
  77.     return 0 ;
  78. }
Add Comment
Please, Sign In to add comment