Advertisement
_no0B

Untitled

Jan 23rd, 2022
807
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.89 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define LL long long
  3. #define N ((int)1e5 + 8)
  4. #define MAX ((int)1e9 + 8)
  5. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  6.  
  7. using namespace std;
  8.  
  9. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // generator
  10.  
  11.  
  12. int GetRandomNumber(int a , int b)
  13. {
  14.     return uniform_int_distribution<int>(a, b)(rng); //rand([a,b])
  15. }
  16.  
  17. int Opp(int a , int b)
  18. {
  19.     return min(a , b);
  20. }
  21.  
  22. void PreProcess(int n , vector < vector < int > >& tab , vector < int >& arr)
  23. {
  24.     for(int i = 1 ; i <= n ; i++) tab[i][0] = arr[i];
  25.     for(int p = 1 ; p <= 20 ; p++){
  26.         for(int i = 1 ; i <= n ; i++){
  27.             tab[i][p] = tab[i][p-1];
  28.             ///int L = (i + 2^p - 1) - 2^(p-1) + 1; => i + 2^p - 2^(p-1) => i + 2^(p-1)
  29.             int L = i + (1<<(p-1));
  30.             if(L <= n) tab[i][p] = Opp(tab[i][p] , tab[L][p-1]);
  31.         }
  32.     }
  33.     /// O(nlogn)
  34.  
  35.     range[1] = 0; /// range[len] = p ; 2^p <= len and 2^(p+1) > len
  36.     for(int i = 2 ; i <= n ; i++){
  37.         range[i] = range[i-1];
  38.         if((i & (i-1)) == 0) range[i]++;
  39.         ///range[i] = range[i/2] + 1;
  40.     }
  41. }
  42.  
  43.  
  44.  
  45. int Query(int L , int R , vector < vector < int > >& tab) /// find minimum, overlapping allowed
  46. {
  47.     if(L > R) return MAX; /// invalid
  48.     int len = R - L + 1;
  49.     int p = range[len];
  50.     ///int i = L + (1<<p) - 1;
  51.     int ans = tab[L][p]; /// green portion
  52.     int i = R - (1<<p) + 1;
  53.     ans = Opp(ans , tab[i][p]) /// blue portion
  54.     return ans;
  55. } /// O(1)
  56.  
  57.  
  58. int Query(int L , int R , vector < vector < int > >& tab) /// find sum, overlapping not allowed
  59. {
  60.     if(L > R) return 0; /// invalid
  61.     int len = R - L + 1;
  62.     int ans = 0;
  63.     for(int p = 0 ; len > 0 ; p++){
  64.         if(len & (1<<p)){
  65.             len -= 1<<p;
  66.             ans = Opp(ans , tab[L][p]);
  67.             L += 1<<p;
  68.         }
  69.     }
  70.     return ans;
  71. } /// O(logn)
  72.  
  73.  
  74.  
  75.  
  76. /// sliding range min / max query
  77.  
  78. bool Usable(int a , int b)
  79. {
  80.     /// min:
  81.     if(a < b) return 1;
  82.     return 0;
  83.  
  84.     /// max:
  85.     if(a > b) return 1;
  86.     return 0;
  87. }
  88.  
  89. void SlidingRange(int n , int len, vector < int >& arr , vector < int >& res)
  90. {
  91.     deque < pair < int , int > > deq; /// (value , index)
  92.     for(int i = 1 ; i <= len ; i++){
  93.         while(!deq.empty()){
  94.             pair < int , int > p = deq.back();
  95.             if(Usable(p.first , arr[i])) break;
  96.             deq.pop_back();
  97.         }
  98.         deq.push_back({arr[i] , i});
  99.     }
  100.  
  101.     res[1] = deq.front().first;
  102.  
  103.     for(int i = 2 ; i + len - 1 <= n ; i++){
  104.         if(deq.front().second < i) deq.pop_front();
  105.         int j = i + len - 1;
  106.         while(!deq.empty()){
  107.             pair < int , int > p = deq.back();
  108.             if(Usable(p.first , arr[j])) break;
  109.             deq.pop_back();
  110.         }
  111.         deq.push_back({arr[j] , j});
  112.         res[i] = deq.front().first;
  113.     }
  114. } /// O(n)
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement