7.CF438D The Child and Sequence 线段树维护区间取模
给定数列,区间查询和,区间取模,单点修改。
记录区间最大值,对于区间最大值小于模数的区间不予更新洛谷传送门:CF438D The Child and Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目分析
给定数列,区间查询和,区间取模,单点修改。
记录区间最大值,对于区间最大值小于模数的区间不予更新,这样更新不会占用较多的时间。
Code
#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
namespace SegTree{
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,
int tree[N << 2], maxx[N << 1], lazy[N << 1];
inline void push_up(int rt){
tree[rt] = tree[ls] + tree[rs];
maxx[rt] = std::max(maxx[ls], maxx[rs]);
}
void build(int rt, int l, int r){
if(l == r){
cin >> tree[rt], maxx[rt] = tree[rt];
return;
}
int mid = l + r >> 1;
build(lson), build(rson);
push_up(rt);
}
void update_part(int rt, int l, int r, int L, int R, int mod){
if(maxx[rt] < mod) return;
if(l == r){
tree[rt] %= mod;
maxx[rt] %= mod;
return;
}
int mid = l + r >> 1;
if(mid >= L) update_part(lson, L, R, mod);
if(mid < R) update_part(rson, L, R, mod);
push_up(rt);
}
void update_single(int rt, int l, int r, int pos, int val){
if(l == r){
tree[rt] = maxx[rt] = val;
return;
}
int mid = l + r >> 1;
if(mid >= pos) update_single(lson, pos, val);
else update_single(rson, pos, val);
push_up(rt);
}
int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int mid = l + r >> 1, ans = 0;
if(mid >= L) ans += query(lson, L, R);
if(mid < R) ans += query(rson, L, R);
return ans;
}
}
#define SEGRG 1, 1,
inline void solve(){
int n, m; cin >> n >> m;
SegTree::build(SEGRG);
while(m--){
int op; cin >> op;
if(op == 1){
int l, r; cin >> l >> r;
cout << SegTree::query(SEGRG, l, r) << endl;
} else if(op == 2) {
int l, r, x; cin >> l >> r >> x;
SegTree::update_part(SEGRG, l, r, x);
} else {
int k, x; cin >> k >> x;
SegTree::update_single(SEGRG, k, x);
}
}
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout << fixed << setprecision(12);
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}