博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
线段树 区间更新(加减乘)模板
阅读量:5360 次
发布时间:2019-06-15

本文共 2968 字,大约阅读时间需要 9 分钟。

#include
using namespace std;const int MAXN = 500000 + 1;const int ADD = 1, MUL = 2;int n, m, p=1e9+7;long long a[MAXN];struct node { long long sum, addv, mulv;}t[MAXN << 2];inline long long read() { long long x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48, ch = getchar(); return x * f;}void Build(int o, int l, int r) { t[o].mulv = 1; if(l == r) t[o].sum = a[l]; else { int mid = (l + r) >> 1; Build(o << 1, l, mid); Build(o << 1|1, mid + 1, r); t[o].sum = (t[o << 1].sum + t[o << 1|1].sum) % p; }}inline void down(int o, int len) { long long mul = t[o].mulv, add = t[o].addv; t[o << 1].sum = (t[o << 1].sum * mul + add * (len - (len >> 1))) % p; t[o << 1|1].sum = (t[o << 1|1].sum * mul + add * (len >> 1)) % p; t[o << 1].mulv = (t[o << 1].mulv * mul) % p; t[o << 1|1].mulv = (t[o << 1|1].mulv * mul) % p; t[o << 1].addv = (t[o << 1].addv * mul + add) % p; t[o << 1|1].addv = (t[o << 1|1].addv * mul + add) % p; t[o].mulv = 1, t[o].addv = 0;}void Update(int o, int l, int r, int ul, int ur, long long v, int fl) { if(ul <= l && r <= ur) { if(fl == 1) { t[o].sum = (t[o].sum + v * (r - l + 1)) % p; t[o].addv = (t[o].addv + v) % p; } else if(fl == 2) { t[o].sum = (t[o].sum * v) % p; t[o].mulv = (t[o].mulv * v) % p; t[o].addv = (t[o].addv * v) % p; } } else { if(t[o].mulv != 1 || t[o].addv) down(o, r - l + 1); int mid = (l + r) >> 1; if(ul <= mid) Update(o << 1, l, mid, ul, ur, v, fl); if(ur > mid) Update(o << 1|1, mid + 1, r, ul, ur, v, fl); t[o].sum = (t[o << 1].sum + t[o << 1|1].sum) % p; }}long long Query(int o, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return t[o].sum % p; int mid = (l + r) >> 1; long long ret = 0; if(t[o].mulv != 1 || t[o].addv) down(o, r - l + 1); if(ql <= mid) ret += Query(o << 1, l, mid, ql, qr); if(qr > mid) ret += Query(o << 1|1, mid + 1, r, ql, qr); return ret % p;}int main(){ n = read(), m = read(); for(int i=1; i<=n; ++i) a[i] = read(); Build(1, 1, n); while(m--) { char s[10]; scanf("%s",s); long long x = read(), y = read(); if(s[0] == 'M') { long long k = read(); Update(1, 1, n, x, y, k, MUL); } else if(s[0] == 'A') { long long k = read(); Update(1, 1, n, x, y, k, ADD); } else if(s[0] == 'S') { long long k = read(); Update(1, 1, n, x, y, k*-1, ADD); } else if(s[0] =='Q') printf("%lld\n", Query(1, 1, n, x, y)); } return 0;}/*5 61 1 1 1 1A 1 3 6S 2 3 3Q 1 3M 1 5 6Q 1 5Q 2 3*/

 

转载于:https://www.cnblogs.com/weimeiyuer/p/9677445.html

你可能感兴趣的文章
受理状态修改为网上申报
查看>>
Spring Cloud服务间调用鉴权
查看>>
centos系统-java -jdk 环境配置
查看>>
JVM调优之服务内存超过阈值报警
查看>>
Android实例-手机安全卫士(三十)-根据指令完成相应操作一(报警音乐和GPS追踪)...
查看>>
消息队列和堆栈
查看>>
结对作业1.1
查看>>
OpenCV学习笔记(8)——图像平滑
查看>>
模型性能提升操作
查看>>
catch that cow
查看>>
我想要的智能电视一键播放体验
查看>>
Djangorestframework之序列化组件
查看>>
Android UI进阶之用gallery实现可滑动的Tab
查看>>
UDP 通信
查看>>
20个强大的jQuery翻书插件【 jQuery flipbook】
查看>>
19、SQL Server 数据修改之Insert into
查看>>
重命名branch
查看>>
漫谈iOS程序的证书和签名机制
查看>>
展开字符串
查看>>
大数据 --> 大数据关键技术
查看>>