之前的线段树1相信大家都做过了。线段树1要求能够实现区间加法和区间查询，那如果再添加一项区间乘呢？
显然，之前我们引入的懒标记是为了更快速的实现区间修改。
但这也仅仅是对于同等级的运算。
因为不同运算等级的运算是无法累积在同一懒标记的。
应该很好理解。就好比你要把你的孩子结点进行区间乘操作，但是你只是把你存储的懒标记乘了一下，是无法达到效果的。
考虑引入两个懒标记。
一个负责存储区间加的懒标记，另外一个负责存储区间乘的。
这样down操作就会变得更加繁琐，因为需要维护的东西多了一个~~ 这谁撑得住 ~~
说说具体实现吧。
题目由三种操作。
区间查询，加，乘。
我们自己需要添加一个down，懒标记下传。
首先建树。~~ 我在这个坑里卡了整整1day ~~
先循环输入n次，用a数组临时存储下来。
然后build（建树）
void build(long long k,long long l,long long r)//建树
{
tree[k].l=l,tree[k].r=r;
tree[k].add_=0,tree[k].mul_=1;
if(l==r)
tree[k].w=a[l];
else
{
int m=(l+r)/2;
build(k*2,l,m);
build(k*2+1,m+1,r);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
tree[k].w%=p;
return;
}
建树和1差不多，不过因为这次是用a数组临时存储的，所以就把scanf改成了赋值而已。另外多了个取模的操作。一样是二分，从根节点开始，往自己的孩子递归，直到叶子结点，然后给叶子结点赋值之后，返回更新当前结点的值。
接下来就是如何同时实现区间乘和区间加了。
虽然有取模操作，但是加法和乘法对于取模这件事是自由的。
但是两种不同运算等级的在线修改怎么实现呢？
引入上面说的两个懒标记。
然后考虑计算的优先级。
因为就只有乘法和加法，分开讨论就行了。
1.加法优先。
会导致一些应该乘的部分没有完成，以及各种奇奇怪怪的问题。
2.乘法优先。
这样的话，修改加法懒标记时就修改，乘法的时候就顺带修改一下加法的就可以了。
似乎2看起来明显比1要好。
那就选择乘法优先！
我和之前一样，结构体里存储了基本的：左端点，右端点，区间值，还加上了两个懒标记。
struct node
{
long long l,r,w;
long long add_,mul_;//懒标记
}tree[4*100000+10];
接下来讲下传操作。
每次需要更新的：
两个儿子结点的区间值、加法懒标记和乘法懒标记，以及清空父节点的懒标记。
因为是乘法优先，那么顺序是：区间值、乘法、加法、清空。
看起来很繁琐实际上只要理解了顺序就行。
void down(long long k)//双懒标记下传
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
tree[k*2].w=(tree[k*2].w*tree[k].mul_+(m-l+1)*tree[k].add_)%p;
tree[k*2+1].w=(tree[k*2+1].w*tree[k].mul_+(r-m)*tree[k].add_)%p;
tree[k*2].mul_=(tree[k*2].mul_*tree[k].mul_)%p;
tree[k*2+1].mul_=(tree[k*2+1].mul_*tree[k].mul_)%p;
tree[k*2].add_=(tree[k*2].add_*tree[k].mul_+tree[k].add_)%p;
tree[k*2+1].add_=(tree[k*2+1].add_*tree[k].mul_+tree[k].add_)%p;
tree[k].mul_=1;
tree[k].add_=0;
return;
}
两个在线修改操作也和之前一样就行了。依然是二分
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return;
if(x<=l&&y>=r)
{
tree[k].w=(tree[k].w*mul)%p;
tree[k].mul_=(tree[k].mul_*mul)%p;
tree[k].add_=(tree[k].add_*mul)%p;
return;
}
down(k);
mu(k*2);
mu(k*2+1);
tree[k].w=(tree[k*2].w+tree[k*2+1].w)%p;
return;
}
void ad(long long k)
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return;
if(x<=l&&y>=r)
{
tree[k].w=(tree[k].w+add*(r-l+1))%p;
tree[k].add_=(tree[k].add_+add)%p;
return;
}
down(k);
ad(k*2);
ad(k*2+1);
tree[k].w=(tree[k*2].w+tree[k*2+1].w)%p;
return;
}
最后是区间查询，还是二分，查到就加上返回。
long long ask(long long k)
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return 0;
if(x<=l&&y>=r)return tree[k].w;
down(k);
return (ask(k*2)+ask(k*2+1))%p;
}
题目门
完整代码贴下面：
using namespace std;
long long n,m,x,y,mul,add;
struct node
{
long long l,r,w;
long long add_,mul_;//懒标记
}tree[4*100000+10];
long long p,a[100010];
void build(long long k,long long l,long long r)//建树
{
tree[k].l=l,tree[k].r=r;
tree[k].add_=0,tree[k].mul_=1;
if(l==r)
tree[k].w=a[l];
else
{
int m=(l+r)/2;
build(k*2,l,m);
build(k*2+1,m+1,r);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
tree[k].w%=p;
return;
}
void down(long long k)//双懒标记下传
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
tree[k*2].w=(tree[k*2].w*tree[k].mul_+(m-l+1)*tree[k].add_)%p;
tree[k*2+1].w=(tree[k*2+1].w*tree[k].mul_+(r-m)*tree[k].add_)%p;
tree[k*2].mul_=(tree[k*2].mul_*tree[k].mul_)%p;
tree[k*2+1].mul_=(tree[k*2+1].mul_*tree[k].mul_)%p;
tree[k*2].add_=(tree[k*2].add_*tree[k].mul_+tree[k].add_)%p;
tree[k*2+1].add_=(tree[k*2+1].add_*tree[k].mul_+tree[k].add_)%p;
tree[k].mul_=1;
tree[k].add_=0;
return;
}
void mu(long long k)
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return;
if(x<=l&&y>=r)
{
tree[k].w=(tree[k].w*mul)%p;
tree[k].mul_=(tree[k].mul_*mul)%p;
tree[k].add_=(tree[k].add_*mul)%p;
return;
}
down(k);
mu(k*2);
mu(k*2+1);
tree[k].w=(tree[k*2].w+tree[k*2+1].w)%p;
return;
}
void ad(long long k)
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return;
if(x<=l&&y>=r)
{
tree[k].w=(tree[k].w+add*(r-l+1))%p;
tree[k].add_=(tree[k].add_+add)%p;
return;
}
down(k);
ad(k*2);
ad(k*2+1);
tree[k].w=(tree[k*2].w+tree[k*2+1].w)%p;
return;
}
long long ask(long long k)
{
long long l=tree[k].l,r=tree[k].r,m=l+(r-l)/2;
if(y<l||r<x)return 0;
if(x<=l&&y>=r)return tree[k].w;
down(k);
return (ask(k*2)+ask(k*2+1))%p;
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--)
{
int ord;
cin>>ord;
if(ord==1)
{
cin>>x>>y>>mul;
mu(1);
}
else if(ord==2)
{
cin>>x>>y>>add;
ad(1);
}
else if(ord==3)
{
cin>>x>>y;
cout<<ask(1)<<endl;
}
}
return 0;
}
ov.