Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define LL long long
- #define N ((int)1e5 + 8)
- #define MAX ((int)1e9 + 8)
- #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // generator
- int GetRandomNumber(int a , int b)
- {
- return uniform_int_distribution<int>(a, b)(rng); //rand([a,b])
- }
- int Opp(int a , int b)
- {
- return min(a , b);
- }
- void PreProcess(int n , vector < vector < int > >& tab , vector < int >& arr)
- {
- for(int i = 1 ; i <= n ; i++) tab[i][0] = arr[i];
- for(int p = 1 ; p <= 20 ; p++){
- for(int i = 1 ; i <= n ; i++){
- tab[i][p] = tab[i][p-1];
- ///int L = (i + 2^p - 1) - 2^(p-1) + 1; => i + 2^p - 2^(p-1) => i + 2^(p-1)
- int L = i + (1<<(p-1));
- if(L <= n) tab[i][p] = Opp(tab[i][p] , tab[L][p-1]);
- }
- }
- /// O(nlogn)
- range[1] = 0; /// range[len] = p ; 2^p <= len and 2^(p+1) > len
- for(int i = 2 ; i <= n ; i++){
- range[i] = range[i-1];
- if((i & (i-1)) == 0) range[i]++;
- ///range[i] = range[i/2] + 1;
- }
- }
- int Query(int L , int R , vector < vector < int > >& tab) /// find minimum, overlapping allowed
- {
- if(L > R) return MAX; /// invalid
- int len = R - L + 1;
- int p = range[len];
- ///int i = L + (1<<p) - 1;
- int ans = tab[L][p]; /// green portion
- int i = R - (1<<p) + 1;
- ans = Opp(ans , tab[i][p]) /// blue portion
- return ans;
- } /// O(1)
- int Query(int L , int R , vector < vector < int > >& tab) /// find sum, overlapping not allowed
- {
- if(L > R) return 0; /// invalid
- int len = R - L + 1;
- int ans = 0;
- for(int p = 0 ; len > 0 ; p++){
- if(len & (1<<p)){
- len -= 1<<p;
- ans = Opp(ans , tab[L][p]);
- L += 1<<p;
- }
- }
- return ans;
- } /// O(logn)
- /// sliding range min / max query
- bool Usable(int a , int b)
- {
- /// min:
- if(a < b) return 1;
- return 0;
- /// max:
- if(a > b) return 1;
- return 0;
- }
- void SlidingRange(int n , int len, vector < int >& arr , vector < int >& res)
- {
- deque < pair < int , int > > deq; /// (value , index)
- for(int i = 1 ; i <= len ; i++){
- while(!deq.empty()){
- pair < int , int > p = deq.back();
- if(Usable(p.first , arr[i])) break;
- deq.pop_back();
- }
- deq.push_back({arr[i] , i});
- }
- res[1] = deq.front().first;
- for(int i = 2 ; i + len - 1 <= n ; i++){
- if(deq.front().second < i) deq.pop_front();
- int j = i + len - 1;
- while(!deq.empty()){
- pair < int , int > p = deq.back();
- if(Usable(p.first , arr[j])) break;
- deq.pop_back();
- }
- deq.push_back({arr[j] , j});
- res[i] = deq.front().first;
- }
- } /// O(n)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement