Segtree ライブラリ
雑なライブラリを切り貼りする生活だったので書いといた。 非再帰・std::function排除なので定数倍は軽め…なはず？
あと、std::functionを排除すると、外でラップしないと使えない。（ので、典型的なクエリはすでにクラスにしてある。）
区間変更が必要なければ上の SegTree を使う。区間変更が必要になったら IntervalSegTree を使う。
fill とか print とか operator[] とか、便利そうな関数も付け加えてある。（大したことはしていない）
template<typename T> class SegTree { protected: unsigned int n = 1, rank = 0; std::vector<T> node; T nodee; virtual T nodef(const T&, const T&)const = 0; public: SegTree(unsigned int m, T init, T nodee):nodee(nodee) { while (n < m) { n *= 2; rank++; } node.resize(2 * n); for (unsigned int i = n; i < 2 * n; i++)node[i] = init; } SegTree(const std::vector<T>& initvec, T nodee):nodee(nodee) { unsigned int m = initvec.size(); while (n < m) { n *= 2; rank++; } node.resize(2 * n); for (unsigned int i = n; i < 2 * n; i++) { if (i - n < m)node[i] = initvec[i - n]; } } virtual void update(int i, T x) { i += n; node[i] = x; while (i != 1) { i >>= 1; node[i] = nodef(node[2 * i], node[2 * i + 1]); } } virtual T query(int l, int r) { l += n; r += n; T ls = nodee, rs = nodee; while (l < r) { if (l & 1) { ls = nodef(ls, node[l]); l++; } if (r & 1) { r--; rs = nodef(node[r], rs); } l >>= 1; r >>= 1; } return nodef(ls, rs); } virtual T operator[](const int& x) { return node[n + x]; } void fill(T x) { std::fill(all(node), x); } void print() { rep(i, n)std::cout << operator[](i) << " "; std::cout << std::endl; } }; class RSQ :public SegTree<lint> { lint nodef(const lint& lhs,const lint& rhs)const{return lhs+rhs;} public: RSQ(int size, const lint& def = 0) :SegTree<lint>(size, def, 0) {} RSQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, 0) {} }; class RMiQ :public SegTree<lint> { lint nodef(const lint& lhs,const lint& rhs)const{return std::min(lhs,rhs);} public: RMiQ(int size, const lint& def = 0) :SegTree<lint>(size, def, LINF) {} RMiQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, LINF) {} }; class RMaQ :public SegTree<lint> { lint nodef(const lint& lhs,const lint& rhs)const{return std::max(lhs,rhs);} public: RMaQ(int size, const lint& def = 0) :SegTree<lint>(size, def, -LINF) {} RMaQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, -LINF) {} }; template<typename T, typename U> class IntervalSegTree :public SegTree<T> { protected: using SegTree<T>::n; using SegTree<T>::rank; using SegTree<T>::node; using SegTree<T>::nodef; using SegTree<T>::nodee; std::vector<U> lazy; std::vector<bool> lazyflag; std::vector<int> width; virtual void lazyf(U&, const U&) = 0; virtual void updf(T&, const U&, const unsigned int&) = 0; void eval(int k) { for (int i = rank; i > 0; i--) { int nk = k >> i; if (lazyflag[nk]) { updf(node[2 * nk], lazy[nk], width[2 * nk]); updf(node[2 * nk + 1], lazy[nk], width[2 * nk + 1]); if (lazyflag[2 * nk])lazyf(lazy[2 * nk], lazy[nk]); else lazy[2 * nk] = lazy[nk]; if (lazyflag[2 * nk + 1])lazyf(lazy[2 * nk + 1], lazy[nk]); else lazy[2 * nk + 1] = lazy[nk]; lazyflag[2 * nk] = lazyflag[2 * nk + 1] = true; lazyflag[nk] = false; } } } public: IntervalSegTree(unsigned int m, T init, T nodee) :SegTree<T>(m, init, nodee) { lazy.resize(2 * n); lazyflag.resize(2 * n); width.resize(2 * n); width[1] = n; for (unsigned int i = 2; i < 2 * n; i++) { width[i] = width[i >> 1] >> 1; } } IntervalSegTree(T nodee, const std::vector<T>& initvec) :SegTree<T>(initvec, nodee) { lazy.resize(2 * n); lazyflag.resize(2 * n); width.resize(2 * n); width[1] = n; for (unsigned int i = 2; i < 2 * n; i++) { width[i] = width[i >> 1] >> 1; } } void update(int i, U x) { i += n; eval(i); updf(node[i], x, width[i]); if (lazyflag[i])lazyf(lazy[i], x); else { lazyflag[i] = true; lazy[i] = x; } while (i /= 2)node[i] = nodef(node[2 * i], node[2 * i + 1]); } void update(int l, int r, U x) { l += n; r += n; int nl = l, nr = r; while (!(nl & 1))nl >>= 1; while (!(nr & 1))nr >>= 1; nr--; eval(nl); eval(nr); while (l < r) { if (l & 1) { updf(node[l], x, width[l]); if (lazyflag[l])lazyf(lazy[l], x); else { lazyflag[l] = true; lazy[l] = x; } l++; } if (r & 1) { r--; updf(node[r], x, width[r]); if (lazyflag[r])lazyf(lazy[r], x); else { lazyflag[r] = true; lazy[r] = x; } } l >>= 1; r >>= 1; } while (nl >>= 1)node[nl] = nodef(node[2 * nl], node[2 * nl + 1]); while (nr >>= 1)node[nr] = nodef(node[2 * nr], node[2 * nr + 1]); } T query(int l, int r) { l += n; r += n; eval(l); eval(r - 1); int ls = nodee, rs = nodee; while (l < r) { if (l & 1) { ls = nodef(ls, node[l]); l++; } if (r & 1) { r--; rs = nodef(node[r], rs); } l >>= 1; r >>= 1; } return nodef(ls, rs); } T operator[](const int& x) { eval(n + x); return node[n + x]; } T queryForAll() { return node[1]; } }; class RAQRSQ :public IntervalSegTree<lint, lint> { lint nodef(const lint& a, const lint& b)const { return a + b; } void lazyf(lint& a, const lint& b) { a += b; } void updf(lint& a, const lint& b, const unsigned int& width) { a += width * b; } public: RAQRSQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, 0) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RAQRSQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>((lint)0, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } }; class RAQRMiQ :public IntervalSegTree<lint, lint> { lint nodef(const lint& a, const lint& b)const { return std::min(a, b); } void lazyf(lint& a, const lint& b) { a += b; } void updf(lint& a, const lint& b, const unsigned int& width) { a += b; } public: RAQRMiQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, LINF) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RAQRMiQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>(LINF, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } }; class RAQRMaQ :public IntervalSegTree<lint, lint> { lint nodef(const lint& a, const lint& b)const { return std::max(a, b); } void lazyf(lint& a, const lint& b) { a += b; } void updf(lint& a, const lint& b, const unsigned int& width) { a += b; } public: RAQRMaQ(unsigned int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, -LINF) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RAQRMaQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>(-LINF, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } }; class RUQRSQ :public IntervalSegTree<lint, lint> { lint nodef(const lint& a, const lint& b)const { return a + b; } void lazyf(lint& a, const lint& b) { a = b; } void updf(lint& a, const lint& b, const unsigned int& width) { a = width * b; } public: RUQRSQ(int size, const int& def = 0) :IntervalSegTree<lint, lint>(size, def, 0) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RUQRSQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>((lint)0, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } }; class RUQRMiQ :public IntervalSegTree<lint, lint> { lint nodef(const int& a, const int& b)const { return std::min(a, b); } void lazyf(int& a, const int& b) { a = b; } void updf(int& a, const int& b, const unsigned int& width) { a = b; } public: RUQRMiQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, LINF) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RUQRMiQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>(LINF, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } }; class RUQRMaQ :public IntervalSegTree<lint, lint> { lint nodef(const lint& a, const lint& b)const { return std::max(a, b); } void lazyf(lint& a, const lint& b) { a = b; } void updf(lint& a, const lint& b, const unsigned int& width) { a = b; } public: RUQRMaQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, -LINF) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } RUQRMaQ(const std::vector<lint>& initvec) :IntervalSegTree<lint, lint>(-LINF, initvec) { for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]); } };
