题意：c++
给定一个长度为n的非负整数序列a，你须要支持如下操做：
1）给定l，r，输出a[l] + a[l+1] + ... + a[r]git
2）给定l，r，x， 将a[l]、a[l+1]、....、a[r]对x取模ui
3）给定k，y，将a[k]修改成yspa
n, m <= 100000，a[i], x, y <= 109code
对于操做（1）（3）很是简单，线段树基本操做blog
问题是操做（2），显然的是咱们不能对区间和取模，这样就很难受get
可是咱们能够想到，一个数如果比模数小，就不须要取模，而一个数w有效取模次数最多为log(w)it
同时单个数被有效取模的一次只会花费O(logn)class
所以每次修改至多使复杂度增长O(lognlogw)date
这样咱们对于区间l, r暴力对每一个能取模的数取模便可
最后时间复杂度为O(mlognlogw)
1 #include<bits/stdc++.h>
2 #define ll long long
3 #define uint unsigned int
4 #define ull unsigned long long
5 using namespace std; 6 const int maxn = 100010; 7 struct shiki { 8 ll maxx, sum; 9 }tree[maxn << 2]; 10 int n, m; 11 ll a[maxn]; 12
13 inline ll read() { 14 ll x = 0, y = 1; 15 char ch = getchar(); 16 while(!isdigit(ch)) { 17 if(ch == '-') y = -1; 18 ch = getchar(); 19 } 20 while(isdigit(ch)) { 21 x = (x << 1) + (x << 3) + ch - '0'; 22 ch = getchar(); 23 } 24 return x * y; 25 } 26
27 inline void maintain(int pos) { 28 int ls = pos << 1, rs = pos << 1 | 1; 29 tree[pos].maxx = max(tree[ls].maxx, tree[rs].maxx); 30 tree[pos].sum = tree[ls].sum + tree[rs].sum; 31 } 32
33 void build(int pos, int l, int r) { 34 if(l == r) { 35 tree[pos].maxx = tree[pos].sum = a[l]; 36 return; 37 } 38 int mid = l + r >> 1; 39 build(pos << 1, l, mid); 40 build(pos << 1 | 1, mid + 1, r); 41 maintain(pos); 42 } 43
44 void get_mod(int pos, int L, int R, int l, int r, ll mod) { 45 if(l > R || r < L) return; 46 if(tree[pos].maxx < mod) return; 47 if(l == r) { 48 tree[pos].sum %= mod; 49 tree[pos].maxx %= mod; 50 return; 51 } 52 int mid = l + r >> 1; 53 get_mod(pos << 1, L, R, l, mid, mod); 54 get_mod(pos << 1 | 1, L, R, mid + 1, r, mod); 55 maintain(pos); 56 } 57
58 void update(int pos, int aim, int l, int r, ll val) { 59 if(l == r && l == aim) { 60 tree[pos].maxx = tree[pos].sum = val; 61 return; 62 } 63 int mid = l + r >> 1; 64 if(aim <= mid) update(pos << 1, aim, l, mid, val); 65 else update(pos << 1 | 1, aim, mid + 1, r, val); 66 maintain(pos); 67 } 68
69 ll query_sum(int pos, int L, int R, int l, int r) { 70 if(l > R || r < L) return 0; 71 if(l >= L & r <= R) return tree[pos].sum; 72 int mid = l + r >> 1; 73 return query_sum(pos << 1, L, R, l, mid) + query_sum(pos << 1 | 1, L, R, mid + 1, r); 74 } 75
76 int main() { 77 n = read(), m = read(); 78 for(int i = 1; i <= n; ++i) a[i] = read(); 79 build(1, 1, n); 80 for(int i = 1; i <= m; ++i) { 81 int opt = read(), x = read(), y = read(); 82 if(opt == 1) printf("%I64d\n", query_sum(1, x, y, 1, n)); 83 if(opt == 2) { 84 ll p = read(); 85 get_mod(1, x, y, 1, n, p); 86 } 87 if(opt == 3) update(1, x, 1, n, y); 88 } 89 return 0; 90 }