上海今天发生的重大新闻5条,河南网站seo费用,烟台网站建设比较大的,wordpress首页显示友情链接文章目录 1.题目[AHOI2009] 维护序列 2.懒标记处理先加后乘的形式1. 先加后乘的操作 先乘后加的形式2. 先乘后加的操作**乘法操作****加法操作** 懒标记的下传 3.代码 1.题目
题目来源:https://www.luogu.com.cn/problem/P2023
[AHOI2009] 维护序列
题目背景
老师交给小可可… 文章目录 1.题目[AHOI2009] 维护序列 2.懒标记处理先加后乘的形式1. 先加后乘的操作 先乘后加的形式2. 先乘后加的操作**乘法操作****加法操作** 懒标记的下传 3.代码 1.题目
题目来源:https://www.luogu.com.cn/problem/P2023
[AHOI2009] 维护序列
题目背景
老师交给小可可一个维护数列的任务现在小可可希望你来帮他完成。
题目描述
有一个长为 n n n 的数列 { a n } \{a_n\} {an}有如下三种操作形式
格式 1 t g c表示把所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 改为 a i × c a_i\times c ai×c ;格式 2 t g c 表示把所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 改为 a i c a_ic aic ;格式 3 t g 询问所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 的和由于答案可能很大你只需输出这个数模 p p p 的值。
输入格式
第一行两个整数 n n n 和 p p p。
第二行含有 n n n 个非负整数表示数列 { a i } \{a_i\} {ai} 。
第三行有一个整数 m m m表示操作总数。
从第四行开始每行描述一个操作同一行相邻两数之间用一个空格隔开每行开头和末尾没有多余空格。
输出格式
对每个操作 3按照它在输入中出现的顺序依次输出一行一个整数表示询问结果。 2.懒标记处理
先加后乘的形式
假设我们要在一个区间上做更新操作区间内的某个数的值用 x x x 表示add 和 mul 分别代表加法因子和乘法因子。
1. 先加后乘的操作
先加后乘的更新过程是 我们想在区间上的每个元素先加一个数 a a a再乘以一个数 m m m这个操作可以表示为 ( x add ) ∗ mul (x \text{add}) * \text{mul} (xadd)∗mul 乘法更新 假设当前要在区间上乘以 a a a则操作变成 ( x add ) ∗ mul ∗ a (x \text{add}) * \text{mul} * a (xadd)∗mul∗a 新的乘法标记将变为 mul ∗ a \text{mul} * a mul∗a这是可以接受的。 加法更新 假设现在要在区间上加上 a a a则变成 ( x add ) ∗ mul a (x \text{add}) * \text{mul} a (xadd)∗mula 这个表达式不容易简化成一种标准形式。我们可以尝试将其转换为 ( x add a mul ) ∗ mul (x \text{add} \frac{a}{\text{mul}}) * \text{mul} (xaddmula)∗mul 然而这样得到的 add 标记变成了 add a mul \text{add} \frac{a}{\text{mul}} addmula这个值可能是一个小数很难表示或处理。因此先加后乘的形式并不理想。
先乘后加的形式
2. 先乘后加的操作
另一种常见的更新方式是先乘后加即首先进行乘法操作然后再进行加法操作。我们可以表示为 x ∗ mul add x * \text{mul} \text{add} x∗muladd
乘法操作
如果我们在这个数上乘以 m m m则更新如下 ( x ∗ mul add ) ∗ m x ∗ mul ∗ m add ∗ m (x * \text{mul} \text{add}) * m x * \text{mul} * m \text{add} * m (x∗muladd)∗mx∗mul∗madd∗m
因此
新的乘法标记变成了 mul ∗ m \text{mul} * m mul∗m。新的加法标记变成了 add ∗ m \text{add} * m add∗m。
加法操作
如果我们在这个数上加上 a a a则更新如下 x ∗ mul add a x * \text{mul} \text{add} a x∗muladda
这里
新的加法标记变为 add a \text{add} a adda。乘法标记保持不变。
懒标记的下传
考虑区间树的情况假设父节点有乘法标记 m m m 和加法标记 a a a其更新表达式为 ( x ∗ mul add ) ∗ m a x ∗ mul ∗ m add ∗ m a (x * \text{mul} \text{add}) * m a x * \text{mul} * m \text{add} * m a (x∗muladd)∗max∗mul∗madd∗ma 左右孩子节点的 sum 更新为 root.sum ∗ m ( root.r − root.l 1 ) ∗ a \text{root.sum} * m (\text{root.r} - \text{root.l} 1) * a root.sum∗m(root.r−root.l1)∗a 这是一个标准的加法和乘法更新可以继续进行懒标记下传。 乘法标记mul下传时更新为 mul ∗ m \text{mul} * m mul∗m 加法标记add下传时更新为 add ∗ m a \text{add} * m a add∗ma 3.代码
//为什么先加后乘的形式不可以
//我们要变成(xadd)*mul的形式
//假设现在要在这个区间上乘 a
//那么这个数就变成了 (xadd)*mul*a
//新的mul标记就变成了 mul*a 这个是可以的
//假设现在要在这个区间上加 a
//那么这个数就变成了 (xadd)*mul a
//化成上面的形式 (xadd a/mul)*mul
//显然新的add标记(add a/mul)可能是个小数不好表示故而这种方式不合适//先乘后加形式
// x*mul add的形式
// 在这个数上乘m
// (x*muladd)*m
// x*mul*m add*m
// 新的mul标记就变成了 mul*m
// 新的add标记就变成了 add*m
// 在这个数上加a
// x*mul add a
// mul标记不变
// 新的add标记就变成了 add a
// pushdown的时候为什么l和r的懒标记怎么改
// 显然父亲结点的mul和add就是以先乘后加的形式下传
// 假设父亲结点为m和a
// (x*muladd)*m a
// x*mul*m add*ma
// 左右孩子的 sum (root.sum*m(root.r-root.l1)*add)
// mul : mul*m
// add : add*ma#include cstdio
#include iostream
using namespace std;
#define int long long
typedef long long ll;
using LL long long;
const int N 1e5 10;
int n, p, m;
int w[N];
struct Node{int l, r, sum, add, mul;
} tr[4 * N];void pushup(int u)
{tr[u].sum (tr[u1].sumtr[u1|1].sum)%p;
}void cale(Node root, int a, int m)
{root.sum (ll)((ll)(root.sum)*m (ll)(root.r-root.l 1)*a)%p;root.add (ll)(root.add*ma)%p;root.mul (ll)root.mul*m%p;
}void pushdown(int u)
{Node root tr[u], left tr[u1], right tr[u1|1];cale(left,root.add,root.mul);cale(right,root.add,root.mul);tr[u].add0;tr[u].mul1;
}void build(int u, int l, int r)
{if(lr){tr[u]{l,r,w[l],0,1};}else{tr[u]{l,r,0,0,1};int mid lr1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);}
}void modify(int u, int l, int r, int add, int mul)
{if(tr[u].lltr[u].rr){cale(tr[u],add,mul);}else{pushdown(u);int mid tr[u].ltr[u].r1;if(lmid)modify(u1,l,r,add,mul);if(r mid)modify(u1|1,l,r,add,mul);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].ll tr[u].rr)return tr[u].sum;else{pushdown(u);int mid tr[u].ltr[u].r1;ll res 0;if(lmid)res query(u1,l,r)%p;if(r mid)res (resquery(u1|1,l,r))%p;return res;}
}signed main()
{cinnp;for(int i1;in;i)cinw[i];build(1,1,n);cinm;while ( m -- ){int t, l, r, d;cintlr;if ( t 1 ) {cind;modify(1, l, r, 0, d);}else if ( t 2 ){cind;modify(1, l, r, d, 1);}else coutquery(1, l, r)\n;}return 0;
}
