_bzoj1798 [Ahoi2009]Seq 维护序列seq【线段树 lazy tag】

时间:2022-01-31 01:26:59

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1798

注意,应保证当前节点维护的值是正确的,lazy tag只是一个下传标记,在下传时应即时更新儿子的维护值,在修改时也应即时更新当前节点的维护值。

#include <cstdio>

const int maxn = 100005;

int n, mod, a[maxn], m, t1, t2, t3, opr;
struct Node {
int ql, qr;
long long sm, mul, add;
} tree[maxn << 2]; inline void pushup(int p) {
tree[p].sm = (tree[p << 1].sm + tree[p << 1 | 1].sm) % mod;
}
inline void pushdown(int p) {
tree[p << 1].mul = tree[p << 1].mul * tree[p].mul % mod;
tree[p << 1].add = (tree[p << 1].add * tree[p].mul + tree[p].add) % mod;
tree[p << 1].sm = (tree[p << 1].sm * tree[p].mul + tree[p].add * (tree[p << 1].qr - tree[p << 1].ql + 1)) % mod; tree[p << 1 | 1].mul = tree[p << 1 | 1].mul * tree[p].mul % mod;
tree[p << 1 | 1].add = (tree[p << 1 | 1].add * tree[p].mul + tree[p].add) % mod;
tree[p << 1 | 1].sm = (tree[p << 1 | 1].sm * tree[p].mul + tree[p].add * (tree[p << 1 | 1].qr - tree[p << 1 | 1].ql + 1)) % mod; tree[p].mul = 1;
tree[p].add = 0;
}
void make_tree(int p, int left, int right) {
tree[p].ql = left;
tree[p].qr = right;
tree[p].mul = 1;
if (left == right) {
tree[p].sm = (long long)(a[left] % mod);
return;
}
int mid = (left + right) >> 1;
make_tree(p << 1, left, mid);
make_tree(p << 1 | 1, mid + 1, right);
pushup(p);
}
void mull(int p, int left, int right, int c) {
if (tree[p].ql == left && tree[p].qr == right) {
tree[p].mul = tree[p].mul * (long long)c % mod;
tree[p].add = tree[p].add * (long long)c % mod;
tree[p].sm = tree[p].sm * (long long)c % mod;
return;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) {
mull(p << 1, left, right, c);
}
else if (left > mid) {
mull(p << 1 | 1, left, right, c);
}
else {
mull(p << 1, left, mid, c);
mull(p << 1 | 1, mid + 1, right, c);
}
pushup(p);
}
void addd(int p, int left, int right, int c) {
if (tree[p].ql == left && tree[p].qr == right) {
tree[p].add = (tree[p].add + (long long)c) % mod;
tree[p].sm = (tree[p].sm + (long long)c * (long long)(tree[p].qr - tree[p].ql + 1)) % mod;
return;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) {
addd(p << 1, left, right, c);
}
else if (left > mid) {
addd(p << 1 | 1, left, right, c);
}
else {
addd(p << 1, left, mid, c);
addd(p << 1 | 1, mid + 1, right, c);
}
pushup(p);
}
int qry(int p, int left, int right) {
if (tree[p].ql == left && tree[p].qr == right) {
return (int)tree[p].sm;
}
pushdown(p);
int mid = (tree[p].ql + tree[p].qr) >> 1, rt;
if (right <= mid) {
rt = qry(p << 1, left, right);
}
else if (left > mid) {
rt = qry(p << 1 | 1, left, right);
}
else {
rt = qry(p << 1, left, mid);
rt = (rt + qry(p << 1 | 1, mid + 1, right)) % mod;
}
pushup(p);
return rt;
} int main(void) {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d%d", &n, &mod);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
make_tree(1, 1, n);
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &opr, &t1, &t2);
if (opr == 1) {
scanf("%d", &t3);
mull(1, t1, t2, t3);
}
else if (opr == 2) {
scanf("%d", &t3);
addd(1, t1, t2, t3);
}
else {
printf("%d\n", qry(1, t1, t2));
}
}
return 0;
}

  

_bzoj1798 [Ahoi2009]Seq 维护序列seq【线段树 lazy tag】的更多相关文章

  1. 【BZOJ1798】【AHOI2009】维护序列(线段树)

    题目链接 题解 这不就是luogu的线段树2的板子吗.... 没有任何的区别... 上代码吧... #include<iostream> #include<cstdio> #i ...

  2. BZOJ 1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq&lpar; 线段树 &rpar;

    线段树.. 打个 mul , add 的标记就好了.. 这个速度好像还挺快的...( 相比我其他代码 = = ) 好像是#35.. ---------------------------------- ...

  3. bzoj 1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq 线段树 区间乘法区间加法 区间求和

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeO ...

  4. Bzoj 1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq&lpar;线段树区间操作&rpar;

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec Memory Limit: 64 MB Description 老师交给小可可一个维护数列的任务,现在小可 ...

  5. BZOJ1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq&lbrack;线段树&rsqb;

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MBSubmit: 5504  Solved: 1937[Submit ...

  6. bzoj 1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq &lpar;线段树 ,多重标记下放)

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MBSubmit: 7773  Solved: 2792[Submit ...

  7. 1798&colon; &lbrack;Ahoi2009&rsqb;Seq 维护序列seq

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MBSubmit: 2930  Solved: 1087[Submit ...

  8. BZOJ&lowbar;1798&lowbar;&lbrack;AHOI2009&rsqb;维护序列&lowbar;线段树

    BZOJ_1798_[AHOI2009]维护序列_线段树 题意:老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成. 有长为N的数列,不妨设为a1,a2,…,aN .有如下三种操作形式: ( ...

  9. &lbrack;AHOI 2009&rsqb; 维护序列(线段树模板题)

    1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Description 老师交给小可可一个维护数列的任务,现在小 ...

随机推荐

  1. 转载自jguangyou的博客,XML基本属性大全

    android:layout_width 指定组件布局宽度 android:layout_height 指定组件布局高度 android:alpha 设置组件透明度 android:backgroun ...

  2. 移植到Windows CE 的经验

    Windows CE 是微软早期推出的嵌入式设备和移动设备的开发运行平台,虽然目前移动端几乎都是android和ios的天下,但是,在嵌入式设备领域,Windows CE仍然占有一块地盘.很多用户希望 ...

  3. 【BZOJ】1103&colon; &lbrack;POI2007&rsqb;大都市meg

    http://www.lydsy.com/JudgeOnline/problem.php?id=1103 题意:一棵n节点的树(1<=n<=250000),m条边(1<=m<= ...

  4. AE 栅格数据使用总结

    RasterBand)的数据组成,一个波段就是一个数据矩阵.对于格网数据(DEM数据)和单波段的影像数据,表现为仅仅只有一个波段数据的栅格数据集,而对于多光谱影像数据则表现为具有多个波段的栅格数据集. ...

  5. Gluon炼丹(Kaggle 120种狗分类,迁移学习加双模型融合)

    这是在kaggle上的一个练习比赛,使用的是ImageNet数据集的子集. 注意,mxnet版本要高于0.12.1b2017112. 下载数据集. train.zip test.zip labels ...

  6. ssh转发代理:ssh-agent用法详解

    SSH系列文章: SSH基础:SSH和SSH服务 SSH转发代理:ssh-agent用法详解 SSH隧道:端口转发功能详解 使用ssh-agent之前 使用ssh公钥认证的方式可以免去ssh客户端(如 ...

  7. Secret Message ---- &lpar;Trie树应用&rpar;

    Secret Message   总时间限制:  2000ms  内存限制:  32768kB 描述 Bessie is leading the cows in an attempt to escap ...

  8. 元组拆包 与 python拆包

    一.元组拆包(元组解包.迭代解包) 元组拆包可以应用到任何可迭代对象上(任何迭代对象),被可迭代对象中的元素数量必须要跟接受这些元素的元组的空档数一致.也可以使用用 * 来表示忽略多余的元素. 一般的 ...

  9. PyQt&plus;Html&plus;Js

    先做记录,后面有时间在仔细研究 https://www.cnblogs.com/jiangjh5/p/7209315.html?utm_source=itdadao&utm_medium=re ...

  10. 代码参考: css3动画—— 星系轨道

    CSS3橙色的星球绕轨道公转动画 http://hovertree.com/texiao/css3/24/ 例子 http://hovertree.com/h/bjaf/css3xingxi.htm ...