# Untitled

Jan 23rd, 2022
741
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
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.