之前的線段樹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;
} 兩個線上修改操作也和之前一樣就行了。依然是二分
cppvoid 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;
} 題目門
完整代碼貼下面：
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.
轉載于:https://www.cnblogs.com/moyujiang/p/11384812.html