aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Data Structures/dynamic_segment_tree_2d.cpp8
-rw-r--r--Data Structures/fenwick_tree.cpp13
-rw-r--r--Data Structures/seg_fenwick_tree.cpp2
-rw-r--r--Data Structures/seg_ordered_set_tree.cpp8
-rw-r--r--Data Structures/segment_tree.cpp4
-rw-r--r--Data Structures/union-find_disjoint_set.cpp6
-rw-r--r--Graph/centroid.cpp6
-rw-r--r--Graph/lca.cpp11
-rw-r--r--Graph/tarjan_scc.cpp6
-rw-r--r--Math/numtheory.cpp3
-rw-r--r--Miscellaneous/util.cpp7
-rw-r--r--Template/template.cpp8
-rw-r--r--Template/usaco.cpp15
13 files changed, 49 insertions, 48 deletions
diff --git a/Data Structures/dynamic_segment_tree_2d.cpp b/Data Structures/dynamic_segment_tree_2d.cpp
index 6948421..fe81b97 100644
--- a/Data Structures/dynamic_segment_tree_2d.cpp
+++ b/Data Structures/dynamic_segment_tree_2d.cpp
@@ -3,7 +3,7 @@ struct y_node {
y_node* c[2];
y_node() { val = 0; c[0] = c[1] = 0; }
y_node* get_c(int i) { return (!c[i] ? c[i] = new y_node : c[i]); }
- void update(int y, int v, int l = -1, int r = MN) {
+ void update(int y, int v, int l = -1, int r = MX) {
if (l == r) val += v;
else {
int m = (l + r) >> 1;
@@ -11,7 +11,7 @@ struct y_node {
val = (c[0] ? c[0]->val : 0) + (c[1] ? c[1]->val : 0);
}
}
- int query(int yl, int yr, int l = -1, int r = MN) {
+ int query(int yl, int yr, int l = -1, int r = MX) {
if (yl > r || yr < l) return 0;
if (yl <= l && yr >= r) return val;
int m = (l + r) >> 1;
@@ -24,7 +24,7 @@ struct x_node {
x_node* c[2];
x_node() { c[0] = c[1] = 0;}
x_node* get_c(int i) { return (!c[i] ? c[i] = new x_node : c[i]); }
- void update(int x, int y, int v, int l = -1, int r = MN) {
+ void update(int x, int y, int v, int l = -1, int r = MX) {
if (l == r) seg.update(y, v);
else {
int m = (l + r) >> 1;
@@ -32,7 +32,7 @@ struct x_node {
seg.update(y, (c[0] ? c[0]->seg.query(y, y) : 0) + (c[1] ? c[1]->seg.query(y, y) : 0));
}
}
- int query(int xl, int xr, int yl, int yr, int l = -1, int r = MN) {
+ int query(int xl, int xr, int yl, int yr, int l = -1, int r = MX) {
if (xl > r || xr < l) return 0;
if (xl <= l && xr >= r) return seg.query(yl, yr);
int m = (l + r) >> 1;
diff --git a/Data Structures/fenwick_tree.cpp b/Data Structures/fenwick_tree.cpp
index ba75c58..4f73507 100644
--- a/Data Structures/fenwick_tree.cpp
+++ b/Data Structures/fenwick_tree.cpp
@@ -1,8 +1,9 @@
template<typename T> class fenwick_tree {
-private: vector<T> FT;
+private: int N; T FT[MX];
public:
- fenwick_tree(int N) { FT.assign(N + 5, 0); }
- void update(int x, T val) { if (++x) for (; x < FT.size(); x += x & -x) FT[x] += val; }
- T query(int x) { T ret = 0; if (++x) for (; x; x -= x & -x) ret += FT[x]; return ret; }
- T query(int x, int y) { return query(y) - query(x - 1); }
-}; \ No newline at end of file
+ fenwick_tree(int n) { N = n }
+ fenwick_tree(int n, T A[]) { N = n; memcpy(FT, A, sizeof FT); }
+ void update(int x, T val) { if (++x) for (; x < N; x += x&-x) FT[x] += val; }
+ T query(int x) { T ret = 0; if (++x) for (; x; x -= x&-x) ret += FT[x]; return ret; }
+ T query(int x, int y) { return query(y)-query(x-1); }
+};
diff --git a/Data Structures/seg_fenwick_tree.cpp b/Data Structures/seg_fenwick_tree.cpp
index b3dae30..d0b7066 100644
--- a/Data Structures/seg_fenwick_tree.cpp
+++ b/Data Structures/seg_fenwick_tree.cpp
@@ -22,7 +22,7 @@ struct node {
int m = (l + r) >> 1;
return (c[0] ? c[0]->query(a, b, l, m) : 0) + (c[1] ? c[1]->query(a, b, m + 1, r) : 0);
}
-} FT[MN];
+} FT[MX];
void update(int x, int y, int v) { for (; x < N; x += x & -x) FT[x].update(y, v); }
int query(int x, int y1, int y2) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x].query(y1, y2); return ret; }
diff --git a/Data Structures/seg_ordered_set_tree.cpp b/Data Structures/seg_ordered_set_tree.cpp
index 2a11ee8..efc5815 100644
--- a/Data Structures/seg_ordered_set_tree.cpp
+++ b/Data Structures/seg_ordered_set_tree.cpp
@@ -3,11 +3,11 @@
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
-constexpr int MN = MN;
+constexpr int MX = MX;
-ordered_set<int> S[4 * MN];
+ordered_set<int> S[4 * MX];
-void update(int x, int y, int l = 0, int r = MN, int n = 1) {
+void update(int x, int y, int l = 0, int r = MX, int n = 1) {
if (l != r) {
int m = (l + r) >> 1;
x <= m ? update(x, y, l, m, n << 1) : update(x, y, m + 1, r, n << 1 | 1);
@@ -15,7 +15,7 @@ void update(int x, int y, int l = 0, int r = MN, int n = 1) {
S[n].insert(y);
}
-int query(int xl, int xr, int yl, int yr, int l = 0, int r = MN, int n = 1) {
+int query(int xl, int xr, int yl, int yr, int l = 0, int r = MX, int n = 1) {
if (l > r || l > xr || r < xl) return 0;
if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl);
else {
diff --git a/Data Structures/segment_tree.cpp b/Data Structures/segment_tree.cpp
index a2b1d40..c0f317b 100644
--- a/Data Structures/segment_tree.cpp
+++ b/Data Structures/segment_tree.cpp
@@ -1,5 +1,5 @@
template<typename T> struct seg_tree {
- T seg[4*MN], tmp[4*MN];
+ T seg[4*MX], tmp[4*MX];
inline T pull(const T & a, const T & b) { return a+b; }
inline void push(int l, int r, int n) {
seg[n] += (r-l+1)*tmp[n];
@@ -11,7 +11,7 @@ template<typename T> struct seg_tree {
if (l == r) seg[n] = v;
else {
int m = (l+r)>>1;
- build(l, m, n<<1), build(m+1, r, n<<1|1);
+ build(v, l, m, n<<1), build(v, m+1, r, n<<1|1);
seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
}
diff --git a/Data Structures/union-find_disjoint_set.cpp b/Data Structures/union-find_disjoint_set.cpp
index b47139f..0ffee07 100644
--- a/Data Structures/union-find_disjoint_set.cpp
+++ b/Data Structures/union-find_disjoint_set.cpp
@@ -2,9 +2,9 @@ class UFDS {
private: vector<int> p, rank;
public:
UFDS(int N) {
- p.assign(N + 1, 0);
+ p.assign(N+1, 0);
for (int i = 0; i <= N; i++) p[i] = i;
- rank.assign(N + 1, 0);
+ rank.assign(N+1, 0);
}
int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); }
bool same_set(int i, int j) { return find_set(i) == find_set(j); }
@@ -14,4 +14,4 @@ public:
rank[x] > rank[y] ? p[y] = x : p[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
-}; \ No newline at end of file
+};
diff --git a/Graph/centroid.cpp b/Graph/centroid.cpp
index 0497bf6..4dd5ac1 100644
--- a/Graph/centroid.cpp
+++ b/Graph/centroid.cpp
@@ -1,6 +1,6 @@
-struct centroid {
- int sz[MN], cpar[MN];
- bitset<MN> vis;
+namespace centroid {
+ int sz[MX], cpar[MX];
+ bitset<MX> vis;
void dfs(vector<int> * G, int u, int p = 0) {
sz[u] = 1;
for (int v : G[u]) if (v != p && !vis[v]) dfs(G, v, u), sz[u] += sz[v];
diff --git a/Graph/lca.cpp b/Graph/lca.cpp
index d02598f..38d972e 100644
--- a/Graph/lca.cpp
+++ b/Graph/lca.cpp
@@ -1,5 +1,5 @@
-struct lca {
- int d[MN], L[MN][20];
+namespace lca {
+ int d[MX], L[MX][20];
void dfs(vector<int> * G, int u = 1, int p = 0) {
d[u] = d[p] + 1, L[u][0] = p;
for (int i = 0; i < 18 && L[u][i]; i++) L[u][i + 1] = L[L[u][i]][i];
@@ -7,9 +7,12 @@ struct lca {
}
int lca(vector<int> * G, int u, int v) {
if (d[u] > d[v]) swap(u, v);
- for (int i = 18; i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[v][i];
+ for (int i = 18; i >= 0; --i) if (d[v] - (1 << i) >= d[u]) v = L[v][i];
if (u == v) return u;
- for (int i = 18; i >= 0; i--) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i];
+ for (int i = 18; i >= 0; --i) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i];
return L[u][0];
}
+ inline int dist(vector<int> * G, int u, int v) {
+ return d[u]+d[v]-2*d[lca(G, u, v)];
+ }
}
diff --git a/Graph/tarjan_scc.cpp b/Graph/tarjan_scc.cpp
index 7f89859..a9bad2e 100644
--- a/Graph/tarjan_scc.cpp
+++ b/Graph/tarjan_scc.cpp
@@ -1,7 +1,7 @@
-struct tarjan {
- int cnt, scc_num, scc[MN], in[MN], low[MN];
+namespace tarjan {
+ int cnt, scc_num, scc[MX], in[MX], low[MX];
stack<int> s;
- bitset<MN> ins;
+ bitset<MX> ins;
void tarjan(vector<int> * G, int u) {
low[u] = in[u] = cnt++, ins[u] = 1; s.push(u);
for (int v : G[u]) {
diff --git a/Math/numtheory.cpp b/Math/numtheory.cpp
index a2be7db..d25a984 100644
--- a/Math/numtheory.cpp
+++ b/Math/numtheory.cpp
@@ -9,10 +9,9 @@ inline ll pw(ll base, ll exp) {
}
return res;
}
-
inline ll inv(ll x) { return pw(x, MOD-2); }
-ll fact[MN] = { 1 }, ifact[MN] = { 1 };
+ll fact[MX] = { 1 }, ifact[MX] = { 1 };
inline ll nCr(int n, int k) { return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }
diff --git a/Miscellaneous/util.cpp b/Miscellaneous/util.cpp
deleted file mode 100644
index 2816c2b..0000000
--- a/Miscellaneous/util.cpp
+++ /dev/null
@@ -1,7 +0,0 @@
-template<typename BidirectionalIterator> // Coordinate compression
-void compress(BidirectionalIterator first, BidirectionalIterator last) {
- vector<pair<BidirectionalIterator, int>> tmp;
- for (auto it = first; it != last; ++it) tmp.emplace_back(*it, it-first);
- sort(begin(tmp), end(tmp));
- for (auto it = begin(tmp); it != end(tmp); ++it) (first+it->s) = it-begin(tmp);
-}
diff --git a/Template/template.cpp b/Template/template.cpp
index 80b2748..df2e7ee 100644
--- a/Template/template.cpp
+++ b/Template/template.cpp
@@ -12,8 +12,11 @@
#define rsz resize
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
-#define tr(a, x) for (auto& a : x)
+#define tr(a, x) for (auto & a : x)
#define mem(a, b) memset(a, (b), sizeof(a))
+#define pc __builtin_popcount
+#define clz __builtin_clz
+#define ctz __builtin_ctz
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
using str = string; using ll = long long; using ld = long double; using cd = complex<ld>;
using ii = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>;
@@ -21,7 +24,8 @@ using vi = vector<int>; using vl = vector<ll>; using vd = vector<ld>;
using vii = vector<ii>; using vpl = vector<pl>; using vpd = vector<pd>;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution
-constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1);
+constexpr ld PI = 4*atan((ld)1);
+constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7;
int main() {
if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
diff --git a/Template/usaco.cpp b/Template/usaco.cpp
index f730b4c..9584afc 100644
--- a/Template/usaco.cpp
+++ b/Template/usaco.cpp
@@ -12,8 +12,11 @@
#define rsz resize
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
-#define tr(a, x) for (auto& a : x)
+#define tr(a, x) for (auto & a : x)
#define mem(a, b) memset(a, (b), sizeof(a))
+#define pc __builtin_popcount
+#define clz __builtin_clz
+#define ctz __builtin_ctz
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
using str = string; using ll = long long; using ld = long double; using cd = complex<ld>;
using ii = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>;
@@ -21,14 +24,12 @@ using vi = vector<int>; using vl = vector<ll>; using vd = vector<ld>;
using vii = vector<ii>; using vpl = vector<pl>; using vpd = vector<pd>;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution
-constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1);
-void io(const str & s) {
- if (fopen((s+".in").c_str(), "r")) freopen((s+".in").c_str(), "r", stdin), freopen((s+".out").c_str(), "w", stdout);
- ios_base::sync_with_stdio(0), cin.tie(0);
-}
+constexpr ld PI = 4*atan((ld)1);
+constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7;
int main() {
- io("name");
+ ifstream cin("in"); ofstream cout("in");
+ ios_base::sync_with_stdio(0), cin.tie(0);
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2024-12-23 02:04:28 +0000