Submission #2225753

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template <class V = int, bool MAX = true> struct SegmentTree_RAQ_RMQ {
	struct Node {
		V dat;
		V lazy;
		bool flag;
		Node() : dat(0), lazy(0), flag(false) {}
	};

	const int n;
	vector<Node> seg;
	SegmentTree_RAQ_RMQ(int size) : n(1 << (32 - __builtin_clz(size - 1))), seg(n * 2) {};

	void set(int i, const V v) { seg[i + n] = v; }
	void build() { for (int i = n - 1; i > 0; i--) seg[i] = merge(seg[i * 2].dat, seg[i * 2 + 1].dat); }
	void update(int qbegin, int qend, V val) { update_range_rec(1, 0, n, qbegin, qend, val); }
	V query(int qbegin, int qend) { return query_rec(1, 0, n, qbegin, qend); }

private:
	V merge(const V l, const V r) { return MAX ? max(l, r) : min(l, r); }

	void propagate(int node, int l, int r) {
		if (seg[node].flag) {
			seg[node].dat += seg[node].lazy;
			if (r - l > 1) {
				for (int child = 2 * node; child <= 2 * node + 1; child++) {
					seg[child].lazy += seg[node].lazy;
					seg[child].flag = true;
				}
			}
			seg[node].lazy = 0;
			seg[node].flag = false;
		}
	}

	void update_range_rec(int node, int l, int r, int qbegin, int qend, V val) {
		propagate(node, l, r);
		if (r <= qbegin || qend <= l) {
			return;
		}
		if (qbegin <= l && r <= qend) {
			seg[node].lazy = val;
			seg[node].flag = true;
			propagate(node, l, r);
		}
		else {
			int m = (l + r) >> 1;
			update_range_rec(2 * node + 0, l, m, qbegin, qend, val);
			update_range_rec(2 * node + 1, m, r, qbegin, qend, val);
			seg[node].dat = merge(seg[2 * node].dat, seg[2 * node + 1].dat);
		}
	}

	V query_rec(int node, int l, int r, int qbegin, int qend) {
		propagate(node, l, r);
		if (qbegin <= l && r <= qend) {
			return seg[node].dat;
		}
		if (r <= qbegin || qend <= l) {
			return MAX ? numeric_limits<V>::min() : numeric_limits<V>::max();
		}
		int m = (l + r) >> 1;
		return merge(query_rec(2 * node, l, m, qbegin, qend), query_rec(2 * node + 1, m, r, qbegin, qend));
	}
};

template <class V = int> struct SegmentTree_RAQ_RSQ {
	struct Node {
		V dat;
		V lazy;
		bool flag;
		Node() : dat(0), lazy(0), flag(false) {}
	};

	const int n;
	vector<Node> seg;
	SegmentTree_RAQ_RSQ(int size) : n(1 << (32 - __builtin_clz(size - 1))), seg(n * 2) {};

	void set(int i, const V v) { seg[i + n] = v; }
	void build() {for (int i = n - 1; i > 0; i--) seg[i] = merge(seg[i * 2].dat, seg[i * 2 + 1].dat); }
	void update(int qbegin, int qend, V val) { update_range_rec(1, 0, n, qbegin, qend, val); }
	V query(int qbegin, int qend) { return query_rec(1, 0, n, qbegin, qend); }

private:
	V merge(const V l, const V r) {
		return l + r;
	}

	void propagate(int node, int l, int r) {
		if (seg[node].flag) {
			seg[node].dat += seg[node].lazy * (r - l);
			if (r - l > 1) {
				for (int child = 2 * node; child <= 2 * node + 1; child++) {
					seg[child].lazy += seg[node].lazy;
					seg[child].flag = true;
				}
			}
			seg[node].lazy = 0;
			seg[node].flag = false;
		}
	}

	void update_range_rec(int node, int l, int r, int qbegin, int qend, V val) {
		propagate(node, l, r);
		if (r <= qbegin || qend <= l) {
			return;
		}
		if (qbegin <= l && r <= qend) {
			seg[node].lazy = val;
			seg[node].flag = true;
			propagate(node, l, r);
		}
		else {
			int m = (l + r) >> 1;
			update_range_rec(2 * node + 0, l, m, qbegin, qend, val);
			update_range_rec(2 * node + 1, m, r, qbegin, qend, val);
			seg[node].dat = merge(seg[2 * node].dat, seg[2 * node + 1].dat);
		}
	}

	V query_rec(int node, int l, int r, int qbegin, int qend) {
		propagate(node, l, r);
		if (qbegin <= l && r <= qend) {
			return seg[node].dat;
		}
		if (r <= qbegin || qend <= l) {
			return 0;
		}
		int m = (l + r) >> 1;
		return merge(query_rec(2 * node, l, m, qbegin, qend), query_rec(2 * node + 1, m, r, qbegin, qend));
	}
};

template <class V = int, bool MAX = true> struct SegmentTree_RUQ_RMQ {
	struct Node {
		V dat;
		V lazy;
		bool flag;
		Node() : dat(0), lazy(0), flag(0) {}
	};

	const int n;
	vector<Node> seg;
	SegmentTree_RUQ_RMQ(int size) : n(1 << (32 - __builtin_clz(size - 1))), seg(n * 2) {};

	void set(int i, const V v) { seg[i + n] = v; }
	void build() {for (int i = n - 1; i > 0; i--) seg[i] = merge(seg[i * 2].dat, seg[i * 2 + 1].dat); }
	void update(int qbegin, int qend, V val) { update_range_rec(1, 0, n, qbegin, qend, val); }
	V query(int qbegin, int qend) { return query_rec(1, 0, n, qbegin, qend); }

private:
	V merge(const V l, const V r) { return MAX ? max(l, r) : min(l, r); }

	void propagate(int node, int l, int r) {
		if (seg[node].flag) {
			seg[node].dat = seg[node].lazy;
			if (r - l > 1) {
				for (int child = 2 * node; child <= 2 * node + 1; child++) {
					seg[child].lazy = seg[node].lazy;
					seg[child].flag = true;
				}
			}
			seg[node].lazy = 0;
			seg[node].flag = false;
		}
	}

	void update_range_rec(int node, int l, int r, int qbegin, int qend, V val) {
		propagate(node, l, r);
		if (r <= qbegin || qend <= l) {
			return;
		}
		if (qbegin <= l && r <= qend) {
			seg[node].lazy = val;
			seg[node].flag = true;
			propagate(node, l, r);
		}
		else {
			int m = (l + r) >> 1;
			update_range_rec(2 * node + 0, l, m, qbegin, qend, val);
			update_range_rec(2 * node + 1, m, r, qbegin, qend, val);
			seg[node].dat = merge(seg[2 * node].dat, seg[2 * node + 1].dat);
		}
	}

	V query_rec(int node, int l, int r, int qbegin, int qend) {
		propagate(node, l, r);
		if (qbegin <= l && r <= qend) {
			return seg[node].dat;
		}
		if (r <= qbegin || qend <= l) {
			return MAX ? numeric_limits<V>::min() : numeric_limits<V>::max();
		}
		int m = (l + r) >> 1;
		return merge(query_rec(2 * node, l, m, qbegin, qend), query_rec(2 * node + 1, m, r, qbegin, qend));
	}
};

template <class V=int> struct SegTreeLazyBest {
	const int n;
	vector<V> cur, lazy, best, best_lazy;

	SegTreeLazyBest(int size) : n(p2(size)), cur(n * 2), lazy(n * 2), best(n * 2), best_lazy(n * 2){};

	void update(int begin, int end, V val) {
		update_range_rec(1, 0, n, begin, end, val);
	}

	V query(int begin, int end) {
		return query_rec(1, 0, n, begin, end);
	}

private:
	void propagate(int node) {
		for (int child = 2 * node; child <= 2 * node + 1; child++) {
			best_lazy[child] = max(best_lazy[child], lazy[child] + best_lazy[node]);
			lazy[child] += lazy[node];
			best[child] = max(best[child], cur[child] + best_lazy[node]);
			cur[child] += lazy[node];
		}
		lazy[node] = best_lazy[node] = 0;
	}

	void update_range_rec(int node, int tbegin, int tend, int abegin, int aend, V val) {
		if (abegin <= tbegin && tend <= aend) {
			best_lazy[node] = max(best_lazy[node], lazy[node] += val);
			best[node] = max(best[node], cur[node] += val);
		}
		else {
			propagate(node);
			int mid = tbegin + (tend - tbegin + 1) / 2;
			if (abegin < mid && tbegin < aend) update_range_rec(2 * node, tbegin, mid, abegin, aend, val);
			if (abegin < tend && mid < aend) update_range_rec(2 * node + 1, mid, tend, abegin, aend, val);
			cur[node] = max(cur[2 * node], cur[2 * node + 1]);
			best[node] = max(best[node], cur[node]);
		}
	}

	V query_rec(int node, int tbegin, int tend, int abegin, int aend) {
		if (abegin <= tbegin && tend <= aend) {
			return best[node];
		}
		else {
			propagate(node);
			int mid = tbegin + (tend - tbegin + 1) / 2;
			V res = numeric_limits<V>::min();
			if (abegin < mid && tbegin < aend) res = max(res, query_rec(2 * node, tbegin, mid, abegin, aend));
			if (abegin < tend && mid < aend) res = max(res, query_rec(2 * node + 1, mid, tend, abegin, aend));
			return res;
		}
	}

	static int p2(int n, int m=1) { return m >= n ? m : p2(n, m * 2); }
};


template <class V> struct SegTreeLazy {
	static const V zero = 0;
	static const V def = 0;
	struct Node {
		V dat;
		V lazy;
		bool flag;
		Node() : dat(def), lazy(zero), flag(false) {}
	};

	static V merge(const V &l, const V &r) {
		return l + r;
		return max(l, r);
	}

	const int N;
	vector<Node> seg;

	SegTreeLazy(int size) : N(p2(size)), seg(N * 2) {};

	void set(int i, const V &v) { seg[i + N - 1].dat = v; }

	void build() { for (int i = N - 2; i >= 0; i--) seg[i].dat = merge(seg[i * 2 + 1].dat, seg[i * 2 + 2].dat); }

	void update(int a, int b, V v) {
		update(a, b, v, 0, 0, N);
	}

	V query(int a, int b) {
		return query(a, b, 0, 0, N);
	}

	private:
	void push_add(int k, int l, int r) {
		if (seg[k].flag) {
			seg[k].dat += seg[k].lazy * (r - l);
			seg[k].dat += seg[k].lazy;
			if (r - l > 1) {
				seg[k * 2 + 1].lazy += seg[k].lazy;
				seg[k * 2 + 2].lazy += seg[k].lazy;
				seg[k * 2 + 1].flag = true;
				seg[k * 2 + 2].flag = true;
			}
			seg[k].lazy = zero;
			seg[k].flag = false;
		}
	}

	void push_update(int k, int l, int r) {
		if (seg[k].flag) {
			seg[k].dat = seg[k].lazy;
			seg[k].dat = seg[k].lazy * (r - l);
			seg[k].dat = merge(seg[k].dat, seg[k].lazy);
			if (r - l > 1) {
				seg[k * 2 + 1].lazy = seg[k].lazy;
				seg[k * 2 + 2].lazy = seg[k].lazy;
				seg[k * 2 + 1].flag = true;
				seg[k * 2 + 2].flag = true;
			}
			seg[k].lazy = zero;
			seg[k].flag = false;
		}
	}

	void update(int a, int b, V v, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			seg[k].lazy = v;
			seg[k].flag = true;
			push(k, l, r);
		}
		else {
			update(a, b, v, k * 2 + 1, l, (l + r) / 2);
			update(a, b, v, k * 2 + 2, (l + r) / 2, r);
			seg[k].dat = merge(seg[k * 2 + 1].dat, seg[k * 2 + 2].dat);
		}
	}

	V query(int a, int b, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return zero;
		if (a <= l && r <= b) return seg[k].dat;
		V x = query(a, b, k * 2 + 1, l, (l + r) / 2);
		V y = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return merge(x, y);
	}

	static int p2(int n, int m=1) { return m >= n ? m : p2(n, m * 2); }
};
template<class Val> ostream& operator<<(ostream& os, const SegTreeLazy<Val>& seg) {
	SegTreeLazy<Val> &seg2 = const_cast<SegTreeLazy<Val>&>(seg);
	vector<Val> vec;
	for (int i = 0; i < seg2.N; i++) {
		vec.emplace_back(seg2.query(i, i+1));
	}
	os << vec;
	return os;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘void SegTreeLazy<V>::update(int, int, V, int, int, int)’:
./Main.cpp:324:15: error: there are no arguments to ‘push’ that depend on a template parameter, so a declaration of ‘push’ must be available [-fpermissive]
   push(k, l, r);
               ^
./Main.cpp:324:15: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
./Main.cpp:329:16: error: there are no arguments to ‘push’ that depend on a template parameter, so a declaration of ‘push’ must be available [-fpermissive]
    push(k, l, r);
                ^
./Main.cpp: In member function ‘V SegTreeLazy<V>::query(int, int, int, int, int)’:
./Main.cpp:339:15: error: there are no arguments to ‘push’ that depend on a template parameter, so a declaration of ‘push’ must be available [-fpermissive]
   push(k, l, r);
               ^