区间最大值、单点修改
#include#include #include #include #include #define re register#define lson o<<1#define rson o<<1|1using namespace std ;const int maxn = 200005 ;inline int read(){ int f = 1 , x = 0 ; char ch = getchar() ; while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar() ;} while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;} return x * f ;}int n , m , a , b ;int tree[maxn * 4] ;inline void pushup(int o) { tree[o] = max(tree[lson] , tree[rson]) ;}inline void build(int o , int l , int r) { if(l == r) { tree[o] = read() ; return ; } int mid = (l + r) / 2 ; build(lson , l , mid) ; build(rson , mid + 1 , r) ; pushup(o) ;}inline int query(int o , int l , int r , int x , int y) { if(x <= l && r <= y) return tree[o] ; int maxx = 0 ; int mid = (l + r) / 2 ; if(x <= mid) maxx = max(maxx , query(lson , l , mid , x , y)) ; if(y > mid) maxx = max(maxx , query(rson , mid + 1 , r , x , y)) ; return maxx ;}inline void update(int o , int l , int r , int x , int y) { if(l == r) { tree[o] = y ; return ; } int mid = (l + r) / 2 ; if(x <= mid) update(lson , l , mid , x , y) ; else update(rson , mid + 1 , r , x , y) ; pushup(o) ;}int main () { freopen("hate it.in" , "r" , stdin) ; n = read () ; m = read () ; build(1 , 1 , n) ; char flag ; while(m--) { cin >> flag ; if(flag == 'Q') { a = read (); b = read () ; printf("%d\n" , query(1 , 1 , n , a , b)) ; } else { a = read () ; b = read () ; update(1 , 1 , n , a , b) ; } } return 0 ;}
例题：
区间最小值、单点修改
#include#include #include #include #include #include #define re registerusing namespace std ;const int maxm = 300005 ;#define lson o<<1#define rson o<<1|1inline int read() { int f = 1 , x = 0 ; char ch = getchar () ; while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar () ;} while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;} return x * f; }int m , n , a , b ;int tree[maxm] ;inline void pushup(int o) { tree[o] = min(tree[lson] , tree[rson]) ;}inline void build(int o , int l , int r) { if(l == r) { tree[o] = read() ; return ; } int mid = (l + r) / 2 ; build(lson , l , mid) ; build(rson , mid + 1 , r) ; pushup(o) ;}inline int query(int o , int l , int r , int x , int y) { if(x <= l && r <= y) return tree[o] ; int minn = 1e9 ; int mid = (l + r) / 2; if(x <= mid) minn = min(minn, query(lson , l , mid , x , y)) ; if(y > mid) minn = min(minn, query(rson , mid + 1 , r , x , y)) ; return minn;}inline void update(int o , int l , int r , int x , int y) { if(l == r) { tree[o] = max(tree[o] , y) ; return ; } int mid = (l + r) / 2 ; if(x <= mid) update(lson , l , mid , x , y) ; else update(rson , mid + 1 , r , x , y) ; pushup(o) ;}int main () { m = read () ; n = read () ; build(1 , 1 , m) ; char flag ; while(n --) { cin >> flag ; if(flag == 'Q') { a = read (); b = read () ; printf("%d\n" , query(1 , 1 , m , a , b)) ; } else { a = read () ; b = read () ; update(1 , 1 , m , a , b) ; } } return 0 ;}
例题：
区间求和、区间修改
#include#include #include #include #include #define re register#define lson o<<1#define rson o<<1|1#define ll long longusing namespace std ;const int maxn = 100005 ;inline long long read(){ long long f = 1 , x = 0 ; char ch = getchar() ; while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar() ;} while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;} return x * f ;}long long n , m , x , y , k ;long long tree[maxn * 4] , add[maxn * 4] ;long long flag ;inline void pushup(ll o) { tree[o] = tree[lson] + tree[rson] ;}inline void pushdown(ll o , ll l , ll r) { if(add[o]) { ll mid = (l + r) / 2 ; add[lson] += add[o] ; add[rson] += add[o] ; tree[lson] += (mid - l + 1) * add[o] ; tree[rson] += (r - mid) * add[o] ; add[o] = 0 ; }} inline void build(ll o , ll l , ll r) { if(l == r) { tree[o] = read() ; return ; } int mid = (l + r) >> 1 ; build(lson , l , mid) ; build(rson , mid + 1 , r) ; pushup(o) ;}inline void update(ll o , ll l , ll r , ll x , ll y , ll val) { if(x <= l && r <= y) { tree[o] +=(r - l + 1) * val ; add[o] += val ; return ; } pushdown(o , l , r) ; ll mid = (l + r) / 2 ; if(x <= mid) update(lson , l , mid , x , y , val) ; if(y > mid) update(rson , mid + 1 , r , x , y , val) ; pushup(o) ;}inline ll query(ll o , ll l , ll r , ll x , ll y) { if(x <= l && r <= y) { return tree[o] ; } pushdown(o , l , r) ; int mid = (l + r) / 2 ; ll ans = 0 ; if(x <= mid) ans += query(lson , l , mid , x , y) ; if(y > mid) ans += query(rson , mid + 1 , r , x , y) ; return ans ;}int main() { n = read() ; m = read() ; build(1 , 1 , n) ; while(m--) { flag = read() ; if(flag == 1) { x = read() ; y = read() ; k = read () ; update(1 , 1 , n , x , y , k) ; } else { x = read () ; y = read () ; printf("%lld\n" , query(1 , 1 , n , x , y)) ; } } return 0 ;}
例题：
单点乘、单点加、区间求和
#include#include #include #include #include #define re register#define lson o<<1#define rson o<<1|1#define ll long longusing namespace std ;const int maxn = 100005 ;inline long long read(){ long long f = 1 , x = 0 ; char ch = getchar() ; while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar() ;} while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;} return x * f ;}ll n , m , mod , flag , x , y , k ;ll tree[maxn * 4] , add[maxn * 4] , mul[maxn * 4] ;inline void pushup(ll o) { tree[o] = tree[lson] + tree[rson] ; mul[o] = 1 ;}inline void pushdown(ll o , ll l , ll r) { ll mid = (l + r) / 2 ; if(mul[o] != 1) { mul[lson] = (mul[lson] * mul[o]) % mod ; mul[rson] = (mul[rson] * mul[o]) % mod ; add[lson] = (add[lson] * mul[o]) % mod ; add[rson] = (add[rson] * mul[o]) % mod ; tree[lson] = (tree[lson] * mul[o]) % mod ; tree[rson] = (tree[rson] * mul[o]) % mod ; mul[o] = 1 ; } if(add[o]) { tree[lson] = (tree[lson] + (add[o] * (mid - l + 1)) % mod) % mod ; tree[rson] = (tree[rson] + (add[o] * (r - mid)) % mod) % mod ; add[lson] = (add[lson] + add[o]) % mod ; add[rson] = (add[rson] + add[o]) % mod ; add[o] = 0 ; }}inline void build(ll o , ll l , ll r) { if(l == r) { tree[o] = read() ; return ; } ll mid = (l + r) / 2 ; build(lson , l , mid) ; build(rson , mid + 1 , r) ; pushup(o) ;}inline void Mul(ll o , ll l , ll r , ll x , ll y , ll k) { if(x <= l && r <= y) { tree[o] = (tree[o] * k) % mod ; mul[o] = (mul[o] * k) % mod ; add[o] = (add[o] * k) % mod ; return ; } pushdown(o , l , r) ; ll mid = (l + r) / 2 ; if(x <= mid) Mul(lson , l , mid , x , y , k) ; if(y > mid) Mul(rson , mid + 1 , r , x , y , k) ; pushup(o) ;}inline void Add(ll o , ll l , ll r , ll x , ll y , ll k) { if(x <= l && r <= y) { tree[o] = (tree[o] + (r - l + 1) * k % mod) % mod ; add[o] = (add[o] + k) % mod ; return ; } pushdown(o , l , r) ; ll mid = (l + r) / 2 ; if(x <= mid) Add(lson , l , mid , x , y , k) ; if(y > mid) Add(rson , mid + 1 , r , x , y , k) ; pushup(o) ;}inline ll query(ll o , ll l , ll r , ll x , ll y) { if(x <= l && r <= y) { return tree[o] ; } ll mid = (l + r) / 2 ; ll ans = 0 ; pushdown(o , l , r) ; if(x <= mid) ans = (ans + query(lson , l , mid , x , y)) % mod ; if(y > mid) ans = (ans + query(rson , mid + 1 , r , x , y)) % mod ; return ans % mod ;}int main () { n = read () ; m = read () ; mod = read() ; build(1 , 1 , n) ; while(m --) { flag = read (); if(flag == 1) { x = read () ; y = read () ; k = read() ; Mul(1 , 1 , n , x , y , k) ; } else if(flag == 2) { x = read() ; y = read() ; k = read() ; Add(1 , 1 , n , x , y , k) ; } else { x = read () ; y = read () ; printf("%lld\n" , query(1 , 1 , n , x , y)) ; } } return 0 ;}
例题：