題目來源：洛谷題目描述如題，已知一個數(shù)列，你需要進(jìn)行下面三種操作： 1.將某區(qū)間每一個數(shù)乘上x 2.將某區(qū)間每一個數(shù)加上x 3.求出某區(qū)間每一個數(shù)的和 輸入輸出格式輸入格式： ? 第一行包含三個整數(shù)N、M、P，分別表示該數(shù)列數(shù)字的個數(shù)、操作的總個數(shù)和模數(shù)。 第二行包含N個用空格分隔的整數(shù)，其中第i個數(shù)字表示數(shù)列第i項的初始值。 接下來M行每行包含3或4個整數(shù)，表示一個操作，具體如下： 操作1： 格式：1 x y k 含義：將區(qū)間[x,y]內(nèi)每個數(shù)乘上k 操作2： 格式：2 x y k 含義：將區(qū)間[x,y]內(nèi)每個數(shù)加上k 操作3： 格式：3 x y 含義：輸出區(qū)間[x,y]內(nèi)每個數(shù)的和對P取模所得的結(jié)果 ? 輸出格式： ? 輸出包含若干行整數(shù)，即為所有操作3的結(jié)果。 ? 輸入輸出樣例輸入樣例#1：?5 5 38 1 5 4 2 3 2 1 4 1 3 2 5 1 2 4 2 2 3 5 5 3 1 4輸出樣例#1：? 17 2 說明時空限制：1000ms,128M 數(shù)據(jù)規(guī)模： 對于30%的數(shù)據(jù)：N<=8，M<=10 對于70%的數(shù)據(jù)：N<=1000，M<=10000 對于100%的數(shù)據(jù)：N<=100000，M<=100000 （數(shù)據(jù)已經(jīng)過加強(qiáng)^_^） 樣例說明：
故輸出應(yīng)為17、2（40 mod 38=2） ? 解析： 這道題難點(diǎn)就在有兩種操作，還要分先后順序。線段樹的基本模板就不多說了。 用某高贊題解的話來講： 面對這兩種操作，可以聯(lián)想到線段樹的一個非常好的功能就是lazytag，只計算出確實(shí)需要訪問的區(qū)間的真實(shí)值，其他的保存在lazytag里面，這樣可以近似O(NlogN)的運(yùn)行起來。在嘗試著寫了只有一個lazetag的程序之后我們發(fā)現(xiàn)一個lazytag是不能夠解決問題的，那就上兩個，分別表示乘法意義上的lazytag和加法意義上的lazytag。緊接著想到pushdown操作之后我們又發(fā)現(xiàn)必須在向下傳遞lazytag的時候人為地為這兩個lazytag規(guī)定一個先后順序，排列組合一下只有兩種情況： ①加法優(yōu)先，即規(guī)定好segtree[root*2].value=((segtree[root*2].value segtree[root].add)*segtree[root].mul)%p，問題是這樣的話非常不容易進(jìn)行更新操作，假如改變一下add的數(shù)值，mul也要聯(lián)動變成奇奇怪怪的分?jǐn)?shù)小數(shù)損失精度，我們內(nèi)心是很拒絕的； ②乘法優(yōu)先，即規(guī)定好segtree[root*2].value=(segtree[root*2].value*segtree[root].mul segtree[root].add*(本區(qū)間長度))%p，這樣的話假如改變add的數(shù)值就只改變add，改變mul的時候把a(bǔ)dd也對應(yīng)的乘一下就可以了，沒有精度損失，看起來很不錯。 emmm，我調(diào)了很久就對了。 ? 參考代碼： #include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;
/*
碼前須知：
取余運(yùn)算對加法，減法，乘法，指數(shù)運(yùn)算皆成立，但對除法不成立：
(a b) % p = (a % p b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p)^b) % p
因此，此規(guī)律運(yùn)用得當(dāng)，本題可以降低相當(dāng)多的時間復(fù)雜度。
*/
LL a[N],n,m,P;
struct tree{
LL l,r;
LL sum,add,multi;
}t[N*4];
void built(LL p,LL l,LL r)
{
t[p].multi=1;t[p].add=0;
t[p].l=l;t[p].r=r;
if(l==r){
t[p].sum=a[l];
return;
}
LL mid=(l r)>>1;
built(p<<1,l,mid);
built((p<<1)|1,mid 1,r);
t[p].sum=(t[p<<1].sum t[(p<<1)|1].sum)%P;
}
void spread(LL p)
{
//乘法優(yōu)先原則運(yùn)算
t[p<<1].sum=((t[p].multi*t[p<<1].sum) t[p].add*(t[p<<1].r-t[p<<1].l 1))%P;
t[(p<<1)|1].sum=((t[p].multi*t[(p<<1)|1].sum) t[p].add*(t[(p<<1)|1].r-t[(p<<1)|1].l 1))%P;
//維護(hù)線段樹,依舊是乘法優(yōu)先原則
t[p<<1].multi=(t[p<<1].multi*t[p].multi)%P;
t[(p<<1)|1].multi=(t[(p<<1)|1].multi*t[p].multi)%P;
t[p<<1].add=(t[p].add t[p<<1].add*t[p].multi)%P;//之前寫錯，是因為沒有深入體會乘法優(yōu)先
t[(p<<1)|1].add=(t[(p<<1)|1].add*t[p].multi t[p].add)%P;
//刪除延遲標(biāo)記
t[p].add=0;
t[p].multi=1;
}
LL ask(LL p,LL l,LL r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
spread(p);
LL mid=(t[p].l t[p].r)>>1;
LL val=0;
if(l<=mid) val=(val ask(p<<1,l,r))%P;
if(r>mid) val=(val ask((p<<1)|1,l,r))%P;
return val%P;
}
void change(LL p,LL l,LL r,LL k)
{
//根據(jù)我們規(guī)定的乘法優(yōu)先原則，此處的加法傳遞函數(shù)應(yīng)先進(jìn)行乘法運(yùn)算
if(l<=t[p].l&&t[p].r<=r){
t[p].add=(t[p].add k)%P;
t[p].sum=(t[p].sum k*(t[p].r-t[p].l 1))%P;
return;
}
spread(p);
LL mid=(t[p].l t[p].r)>>1;
if(l<=mid) change(p<<1,l,r,k);
if(r>mid) change((p<<1)|1,l,r,k);
t[p].sum=(t[p<<1].sum t[(p<<1)|1].sum)%P;
}
void multiply(LL p,LL l,LL r,LL k)
{
if(l<=t[p].l&&t[p].r<=r){
t[p].sum=(t[p].sum*k)%P;
t[p].multi=(t[p].multi*k)%P;
t[p].add=(t[p].add*k)%P;//在某區(qū)間的乘法延遲標(biāo)記乘上某數(shù)后，自然的其加法
//延遲標(biāo)記也要乘上去
return;
}
spread(p);
LL mid=(t[p].l t[p].r)>>1;
if(l<=mid) multiply(p<<1,l,r,k);
if(r>mid) multiply((p<<1)|1,l,r,k);
t[p].sum=(t[p<<1].sum t[(p<<1)|1].sum)%P;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&P);
for(int i=1;i<=n;i ) scanf("%lld",&a[i]);
built(1,1,n);
while(m--)
{
LL l,r,k;
int flag;
scanf("%d",&flag);
if(flag==2){
scanf("%lld%lld%lld",&l,&r,&k);
change(1,l,r,k);
}
else if(flag==3){
scanf("%lld%lld",&l,&r);
printf("%lld\n",ask(1,l,r));
}
else{
scanf("%lld%lld%lld",&l,&r,&k);
multiply(1,l,r,k);
}
}
return 0;
}
2019-05-12?13:39:57 |
|
|
