Merge branch 'master' of https://github.com/Ta180m/Library

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);