-
-
Save GoBigorGoHome/82d5c7eaa5ed8f033cfa49f350ca0aee to your computer and use it in GitHub Desktop.
模板化线段树
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#include <ext/pb_ds/assoc_container.hpp> | |
#include <ext/pb_ds/tree_policy.hpp> | |
using namespace std; | |
#define pb push_back | |
#define eb emplace_back | |
#define all(x) x.begin(), x.end() | |
#define debug(x) cerr << #x <<": " << (x) << endl | |
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) | |
#ifdef LOCAL | |
#define see(x) cout << #x << ": " << (x) << endl | |
#endif | |
#ifndef LOCAL | |
#define see(x) | |
#endif | |
#define rep(n) for(int _ = 0; _ != (n); ++_) | |
//#define rep(i, a, b) for(int i = (a); i <= (b); ++i) | |
#define Rng(i, n) for(int i = 0; i != (n); ++i) | |
#define rng(i, a, b) for(int i = (a); i < (b); ++i) | |
#define rno(i, b) for(int i = 0; i<(b); ++i) | |
#define rnc(i, a, b) for(int i = (a); i<=(b); ++i) | |
#define RNG(i, a) for(auto &i: (a)) | |
#define dwn(i, r, l) for(int i = (r); i>=(l); i--) | |
namespace std { | |
template<class T> | |
T begin(std::pair<T, T> p) | |
{ | |
return p.first; | |
} | |
template<class T> | |
T end(std::pair<T, T> p) | |
{ | |
return p.second; | |
} | |
} | |
#if __cplusplus < 201402L | |
template<class Iterator> | |
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it) | |
{ | |
return std::reverse_iterator<Iterator>(it); | |
} | |
#endif | |
template<class Range> | |
std::pair<std::reverse_iterator<decltype(begin(std::declval<Range>()))>, std::reverse_iterator<decltype(begin(std::declval<Range>()))>> make_reverse_range(Range &&r) | |
{ | |
return std::make_pair(make_reverse_iterator(::begin(r)), make_reverse_iterator(::end(r))); | |
} | |
#define RRNG(x, cont) for (auto &x: make_reverse_range(cont)) | |
template<class T> int sign(const T &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; } | |
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);} | |
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);} | |
template<class T> void Min(T &a, const T &b){ a = min(a, b); } | |
template<class T> void Max(T &a, const T &b){ a = max(a, b); } | |
template<typename T> void println(const T &t) { cout << t << '\n'; } | |
template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); } | |
template<typename T> void print(const T &t) { cout << t << ' '; } | |
template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t; print(rest...); } | |
// this overload is chosen when there's only one argument | |
template<class T> void scan(T &t) { cin >> t; } | |
template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); } | |
using ll = long long; | |
using ull = unsigned long long; | |
using vec = vector<ll>; | |
using mat = vector<vec>; | |
using pii = pair<int, int>; | |
using pdd = pair<double, double>; | |
using pip = pair<int, pii>; | |
using szt = size_t; | |
using vi = vector<int>; | |
using vl = vector<ll>; | |
using vb = vector<bool>; | |
using vpii = vector<pii>; | |
using vvi = vector<vi>; | |
using pli = pair<ll,int>; | |
using wg = vector<vpii>; //weighted graph | |
int cas; | |
const double pi = acos(-1); | |
ll mod = 1e9 + 7; | |
//要求:0<=a<mod, 0<=b<=mod | |
template<class T> | |
inline void add_mod(T &a, const T &b) { | |
a += b; | |
if (a >= mod) a -= mod; | |
} | |
template<class T> | |
void sub_mod(T &a, const T &b){ | |
a -= b; | |
if (a < 0) a += mod; | |
} | |
auto bo=[](int x){ | |
bitset<5> a(x); | |
cout << a << endl; | |
}; | |
//返回值:a中比k小的元素有多少个? | |
template<class V, class Cont> | |
int get_rank(const V &k, const Cont &a){ | |
return std::lower_bound(all(a), k) - a.begin(); | |
} | |
mat operator*(const mat &a, const mat &b) { | |
mat c(a.size(), vec(b[0].size())); | |
for (size_t i = 0; i < a.size(); i++) { | |
for (size_t j = 0; j < a[0].size(); j++) { | |
if (a[i][j]) { // optimization for sparse matrix | |
for (size_t k = 0; k < b[0].size(); k++) { | |
add_mod(c[i][k], a[i][j] * b[j][k] % mod); | |
} | |
} | |
} | |
} | |
return c; | |
} | |
vec operator*(const mat &a, const vec &b) { | |
vec c(a.size()); | |
for (size_t i = 0; i < a.size(); i++) { | |
for (size_t j = 0; j < a[0].size(); j++) { | |
add_mod(c[i], a[i][j] * b[j] % mod); | |
} | |
} | |
return c; | |
} | |
mat pow(mat a, ull n) { | |
mat res(a.size(), vec(a[0].size())); | |
for (size_t i = 0; i < a.size(); i++) { | |
res[i][i] = 1; | |
} | |
while (n) { | |
if (n & 1) { | |
res = res * a; | |
} | |
a = a * a; | |
n >>= 1; | |
} | |
return res; | |
} | |
// Codeforces does not support __int128 | |
//std::ostream& operator<<(std::ostream& os, __int128 T) { | |
// if (T<0) os<<"-"; | |
// if (T>=10 ) os<<T/10; | |
// if (T<=-10) os<<(-(T/10)); | |
// return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ; | |
//} | |
// | |
//__int128 LPOW(__int128 x, ll n) { | |
// __int128 res = 1; | |
// for (; n; n /= 2, x *= x, x %= mod) { | |
// if (n & 1) { | |
// res *= x; | |
// res %= mod; | |
// } | |
// } | |
// return res; | |
//} | |
ll POW(ll x, ll n){ | |
ll res = 1; | |
for (; n; n /= 2, x *= x, x %= mod) { | |
if (n & 1) { | |
res *= x; | |
res %= mod; | |
} | |
} | |
return res; | |
} | |
ll INV(ll x) { | |
return POW(x, mod - 2); | |
} | |
ll inv(ll x){ | |
// see(x); | |
return x == 1? 1: (mod - mod/x * inv(mod%x) % mod); | |
} | |
// 2D rotation | |
void rotate(double &x, double &y, double theta) { | |
double tx = cos(theta) * x - sin(theta) * y; | |
double ty = sin(theta) * x + cos(theta) * y; | |
x = tx, y = ty; | |
} | |
template<class node> | |
struct segment_tree{ | |
vector<node> a; | |
using tag = typename node::lazy_tag; | |
segment_tree() = default; | |
inline int lson(int i){return i*2;} | |
inline int rson(int i){return i*2+1;} | |
template<class T> | |
void build(int i, int l, int r, const T *arr){ | |
if(l==r){ | |
a[i] = node(arr[l]); | |
} | |
else{ | |
int mid = (l+r)/2; | |
build(lson(i), l, mid, arr); | |
build(rson(i), mid+1, r, arr); | |
a[i].put_up(a[lson(i)], a[rson(i)]); | |
} | |
} | |
template<class T> | |
segment_tree(const T *arr, int n){ | |
a.resize(4*n); | |
build(1, 1, n, arr); // 1-indexed | |
} | |
void push_down(int i){ | |
a[lson(i)].put_tag(a[i].tag); | |
a[rson(i)].put_tag(a[i].tag); | |
a[i].tag = {}; | |
} | |
template<class T> using UnaryFunction = std::function<T(const node &)>; | |
template<class T> using MergeFunction = std::function<T(T,T)>; | |
template<typename T> | |
T query(int i, int l, int r, int ql, int qr, const UnaryFunction<T> &get_res, const MergeFunction<T> &merge){ | |
if(l > qr || r < ql) return {}; | |
if(ql <= l && r <= qr){ | |
return get_res(a[i]); | |
} | |
int mid = (l+r)/2; | |
push_down(i); | |
return merge(query(lson(i), l, mid, ql, qr, get_res, merge), query(rson(i), mid+1, r, ql, qr, get_res, merge)); | |
} | |
virtual void maintain(int i, int l, int r){}; // 其他维护操作 | |
void change(int i, int l, int r, int ql, int qr, const tag &tag){ | |
if(l > qr || r < ql) return; | |
if(l >= ql && r <= qr){ | |
a[i].put_tag(tag); | |
maintain(i, l, r); | |
} | |
else{ | |
int mid = (l+r)/2; | |
push_down(i); | |
change(lson(i), l, mid, ql, qr, tag); | |
change(rson(i), mid+1, r, ql, qr, tag); | |
a[i].put_up(a[lson(i)], a[rson(i)]); | |
} | |
} | |
}; | |
struct dsu{ | |
vector<int> par; | |
explicit dsu(int n){ // 0-indexed | |
par.resize(n); | |
rng(i, 0, n){ | |
par[i] = i; | |
} | |
} | |
bool same(int x, int y){ | |
return root(x) == root(y); | |
} | |
int root(int x){ | |
return par[x] == x ? x : par[x] = root(par[x]); | |
} | |
void unite(int x, int y){ | |
x = root(x); | |
y = root(y); | |
par[x] = y; | |
} | |
}; | |
struct bit { | |
vector<int> a; | |
vector<int> id; // id[i]:键区间(i-lowbit(i), i]中,x+y取最小值的点的编号 | |
bit(int n, int v = 0, bool manhattan = false) { | |
a.resize(n + 1); | |
for (int i = 1; i <= n; ++i) a[i] = v; | |
if(manhattan){ | |
id.resize(n+1); | |
rng(i, 1, n+1) id[i] = -1; | |
} | |
} | |
ll sum(int x) { | |
ll res = 0; | |
while (x) { | |
res += a[x]; | |
x -= x & -x; | |
} | |
return res; | |
} | |
ll sum(int l, int r) { | |
if (l > r) return 0; | |
return sum(r) - sum(l - 1); | |
} | |
void add(int x, ll v) { | |
while (x < a.size()) { | |
a[x] += v; | |
x += x & -x; | |
} | |
} | |
void min(int x, int v) { | |
while (x < a.size()) { | |
a[x] = std::min(a[x], v); | |
x += x & -x; | |
} | |
} | |
int manhattan_min(int x){ // 返回x+y最小的点的编号 | |
int ans = -1; | |
int res = INT_MAX; | |
while(x){ | |
if(a[x] < res){ | |
res = a[x]; | |
ans = id[x]; | |
} | |
x -= x & - x; | |
} | |
return ans; | |
} | |
void manhattan_min(int x, int v, int i){ | |
while(x < a.size()){ | |
if(a[x] > v){ | |
a[x] = v; | |
id[x] = i; | |
} | |
x += x & - x; | |
} | |
} | |
void max(int x, int v) { | |
while (x < a.size()) { | |
a[x] = std::max(a[x], v); | |
x += x & -x; | |
} | |
} | |
int min(int x) { | |
int res = INT_MAX; | |
while (x) { | |
res = std::min(res, a[x]); | |
x -= x & -x; | |
} | |
return res; | |
} | |
int max(int x) { | |
int res = INT_MIN; | |
while (x) { | |
res = std::max(res, a[x]); | |
x -= x & -x; | |
} | |
return res; | |
} | |
}; | |
namespace util{ | |
int len(ll x){return snprintf(nullptr, 0, "%lld", x);} | |
vi get_d(ll x){ | |
vi res; | |
while(x) { | |
res.pb(x%10); | |
x /= 10; | |
} | |
reverse(all(res)); | |
return res; | |
} | |
template <class T> T parity(const T &a){ | |
return a & 1; | |
} | |
template <class T> | |
void out (const vector<T> &a){ | |
std::copy(a.begin(), a.end(), std::ostream_iterator<T>(std::cout, ", ")); | |
cout << endl; | |
} | |
using order_statistic_tree = __gnu_pbds::tree< | |
int, | |
__gnu_pbds::null_type, | |
greater<int>, | |
__gnu_pbds::rb_tree_tag, | |
__gnu_pbds::tree_order_statistics_node_update>; | |
} | |
using namespace util; | |
const ll LINF = LLONG_MAX/10; | |
const int INF = INT_MAX/10; | |
const int M = 5005; | |
const int N = 1e5+5; | |
int b[N]; | |
struct node{ | |
using lazy_tag = int; | |
int min; int sum; lazy_tag tag; | |
node()=default; | |
explicit node(int x){ | |
min = x; | |
sum = 0; | |
tag = 0; | |
} | |
void put_up(const node &l, const node &r){ | |
min = std::min(l.min, r.min); | |
sum = l.sum + r.sum; | |
} | |
void put_tag(const lazy_tag &ft) {//ft: father's tag | |
tag += ft; | |
min += ft; | |
} | |
}; | |
template <class node> | |
struct tree : segment_tree<node>{ | |
using segment_tree<node>::a; | |
using segment_tree<node>::lson; | |
using segment_tree<node>::rson; | |
using segment_tree<node>::query; | |
using segment_tree<node>::push_down; | |
tree()= default; | |
template<typename T> | |
tree(const T *arr, int n):segment_tree<node>(arr, n){} | |
void maintain(int i, int l, int r) override { | |
if(a[i].min > 0) return; | |
if(l == r){ | |
a[i].sum++; | |
a[i].min = b[l]; | |
} | |
else{ | |
int mid = (l + r)/2; | |
push_down(i); | |
maintain(lson(i), l, mid); | |
maintain(rson(i), mid+1, r); | |
a[i].put_up(a[lson(i)], a[rson(i)]); | |
} | |
} | |
}; | |
int main() { | |
// Single Cut of Failure taught me | |
cout << std::fixed; | |
cout << setprecision(10); | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
#ifdef LOCAL | |
freopen("main.in", "r", stdin); | |
// freopen("main.out", "w", stdout); | |
#endif | |
int n, m; | |
auto get_res = [](const node &i) { return i.sum; }; | |
auto merge = [](const int &i, const int &j) { return i + j; }; | |
while(cin >> n >> m) { | |
rng(i, 1, n + 1) scan(b[i]); | |
tree<node> t(b, n); | |
rep(m) { | |
string op; | |
int l, r; | |
scan(op, l, r); | |
if (op[0] == 'q') { | |
println(t.query<int>(1, 1, n, l, r, get_res, merge)); | |
} else { | |
t.change(1, 1, n, l, r, -1); | |
} | |
} | |
} | |
#ifdef LOCAL | |
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; | |
#endif | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment