首页 > 代码库 > BZOJ1798 [Ahoi2009]Seq 维护序列seq
BZOJ1798 [Ahoi2009]Seq 维护序列seq
线段树很长时间没有写了。。。于是蒟蒻竟然不会了。。。
这棵线段树要维护两个lazy tag：
1、乘的倍数
2、加的数字
每次更新的时候都要注意运算符优先级就可以了。
1 /************************************************************** 2 Problem: 1798 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:3896 ms 7 Memory:10184 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 typedef long long ll; 15 16 struct sgement_tree{ 17 ll sum, mul, add; 18 }seg[400025]; 19 ll mod; 20 int n, M, L, R, X, oper, Mul, Add; 21 22 inline ll read(){ 23 ll x = 0; 24 char ch = getchar(); 25 while (ch < ‘0‘ || ch > ‘9‘) 26 ch = getchar(); 27 28 while (ch >= ‘0‘ && ch <= ‘9‘){ 29 x = x * 10 + ch - ‘0‘; 30 ch = getchar(); 31 } 32 return x; 33 } 34 35 inline void refresh(int p, int D){ 36 int l = p << 1, r = p << 1 | 1; 37 seg[l].sum = (seg[l].sum * seg[p].mul + (D - (D >> 1)) * seg[p].add) % mod; 38 seg[l].mul = seg[l].mul * seg[p].mul % mod; 39 seg[l].add = (seg[l].add * seg[p].mul + seg[p].add) % mod; 40 seg[r].sum = (seg[r].sum * seg[p].mul + (D >> 1) * seg[p].add) % mod; 41 seg[r].mul = seg[r].mul * seg[p].mul % mod; 42 seg[r].add = (seg[r].add * seg[p].mul + seg[p].add) % mod; 43 seg[p].mul = 1, seg[p].add = 0; 44 } 45 46 inline void fresh(int p){ 47 seg[p].sum = (seg[p << 1].sum + seg[p << 1 | 1].sum) % mod; 48 } 49 50 void build_seg(int p, int l, int r){ 51 seg[p].mul = 1, seg[p].add = 0; 52 if (l == r){ 53 seg[p].sum = read(); 54 return; 55 } 56 int mid = (l + r) >> 1; 57 build_seg(p << 1, l, mid); 58 build_seg(p << 1 | 1, mid + 1, r); 59 fresh(p); 60 } 61 62 void update(int p, int l, int r){ 63 if (R < l || r < L) return; 64 if (L <= l && r <= R){ 65 seg[p].sum = (seg[p].sum * Mul + (r - l + 1) * Add) % mod; 66 seg[p].mul = seg[p].mul * Mul % mod; 67 seg[p].add = (seg[p].add * Mul + Add) % mod; 68 return; 69 } 70 int mid = (l + r) >> 1; 71 refresh(p, r - l + 1); 72 update(p << 1, l, mid); 73 update(p << 1 | 1, mid + 1, r); 74 fresh(p); 75 } 76 77 ll query(int p, int l, int r){ 78 if (R < l || r < L) return 0; 79 if (L <= l && r <= R) return seg[p].sum; 80 int mid = (l + r) >> 1; 81 refresh(p, r - l + 1); 82 ll res = (query(p << 1, l, mid) + query(p << 1 | 1, mid + 1, r)) % mod; 83 fresh(p); 84 return res; 85 } 86 87 int main(){ 88 n = read(), mod = read(); 89 build_seg(1, 1, n); 90 M = read(); 91 while (M--){ 92 oper = read(); 93 if (oper == 1){ 94 L = read(), R = read(); 95 Mul = read(), Add = 0; 96 update(1, 1, n); 97 }else 98 if (oper == 2){ 99 L = read(), R = read();100 Mul = 1, Add = read();101 update(1, 1, n);102 }else{103 L = read(), R = read();104 printf("%lld\n", query(1, 1, n));105 }106 }107 return 0;108 }
BZOJ1798 [Ahoi2009]Seq 维护序列seq
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。