-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalgorithms.cpp
More file actions
148 lines (126 loc) · 3.92 KB
/
Copy pathalgorithms.cpp
File metadata and controls
148 lines (126 loc) · 3.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MOD = 1e9 + 7;
const int INF = 1e18;
// !!!: auto& primes = getPrimes();
const vector<int>& getPrimes() {
static const vector<int> primes = []() {
const int MAX_N = 2e5 + 1;
vector<int> temp;
vector<bool> isPrime(MAX_N + 1, true);
for (int i = 2; i * i <= MAX_N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= MAX_N; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= MAX_N; i++) {
if (isPrime[i]) temp.push_back(i);
}
return temp;
}();
return primes;
}
// !!!: auto& isSimple = getIsSimple();
const vector<ll>& getIsSimple() {
static const vector<ll> isSimple = []() {
const vector<int>& primes = getPrimes();
vector<ll> temp(2e5 + 1);
for (ll i : primes) {
temp[i] = 1;
}
return temp;
}();
return isSimple;
}
// Half / semi primes, up to MAX_N numbers that have only two prime factors
const vector<pair<int, int>>& getHalfPrimes() {
static const vector<pair<int, int>> halfPrimes = []() {
const vector<int>& primes = getPrimes();
const int MAX_N = 2e5 + 1;
vector<pair<int, int>> temp(MAX_N + 1, {0, 0});
for (int i = 0; i < primes.size(); ++i) {
for (int j = i; j < primes.size(); ++j) {
if ((long long)primes[i] * primes[j] <= MAX_N) {
temp[primes[i] * primes[j]] = {primes[i], primes[j]};
} else {
break;
}
}
}
return temp;
}();
return halfPrimes;
}
// MinMaxStack to get min/max in O(1)
// See: codeforces/course_2/two-pointers/step_2/F2_stacks.cpp
struct MinMaxStack {
stack<ll> s;
stack<ll> minStack;
stack<ll> maxStack;
void push(ll x) {
s.push(x);
minStack.push(minStack.empty() || x < minStack.top() ? x
: minStack.top());
maxStack.push(maxStack.empty() || x > maxStack.top() ? x
: maxStack.top());
}
ll pop() {
ll x = s.top();
s.pop();
minStack.pop();
maxStack.pop();
return x;
}
ll getMin() { return minStack.top(); }
ll getMax() { return maxStack.top(); }
size_t size() { return s.size(); }
static ll get_min(MinMaxStack& s1, MinMaxStack& s2) {
if (s1.size() == 0) return s2.getMin();
if (s2.size() == 0) return s1.getMin();
return min(s1.getMin(), s2.getMin());
}
static ll get_max(MinMaxStack& s1, MinMaxStack& s2) {
if (s1.size() == 0) return s2.getMax();
if (s2.size() == 0) return s1.getMax();
return max(s1.getMax(), s2.getMax());
}
};
// GCD Segment Tree
// see: codeforces/course_2/two-pointers/step_2/G.cpp
struct SegTreeGCD {
vector<ll> t;
int n;
SegTreeGCD(int n) : n(n) { t.resize(4 * n); }
void build(vector<ll>& a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v] = gcd(t[v * 2], t[v * 2 + 1]);
}
}
ll query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return gcd(query(v * 2, tl, tm, l, min(r, tm)),
query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
ll query(int l, int r) { return query(1, 0, n - 1, l, r); }
};
int binpow(int a, int n, int m = MOD) {
int res = 1;
while (n) {
if (n & 1) res = (res * a) % m;
a = (a * a) % m;
n >>= 1;
}
return res;
}