BZOJ
洛谷

首先可以把原序列\(A_i\)轉(zhuǎn)化成差分序列\(B_i\)去做。
這樣對(duì)于區(qū)間加一個(gè)等差數(shù)列\((l,r,a_0,d)\)，就可以轉(zhuǎn)化為\(B_{l-1}\)+=\(a_0\)，\(B_r\)-=\((r-l)*d+a_0\)，\(B_{l...r-1}\)+=\(d\)。
對(duì)于查詢，似乎只需要求區(qū)間\(b_i\)的連續(xù)段個(gè)數(shù)？
并不是，比如：
\(A:\ 0\ 1\ 3\ 6\ 10\\B:\ \ \ 1\ 2\ 3\ 4\)
答案是\(3\)而不是\(4\)，我們可以這樣劃分：\(\{0,1\},\{3,6\},\{10\}\)，或是\(\{0,1\},\{3\},\{6,10\}\)等等，得到三個(gè)等差數(shù)列。
為什么會(huì)不是\(4\)呢，除了兩個(gè)數(shù)也是一個(gè)等差數(shù)列外，如果我們選擇了差分序列中的\(1,4\)，也就是選\(\{0,1\},\{6,10\}\)劃分成兩個(gè)等差數(shù)列，那\(A_3=3\)是屬于\(B_2=2\)還是\(B_3=3\)呢？
問(wèn)題其實(shí)在于，區(qū)間中間那個(gè)數(shù)只能屬于左右等差數(shù)列中的一個(gè)（或是相等的時(shí)候可以把兩個(gè)等差數(shù)列連起來(lái)）。

然而網(wǎng)上好多題解都沒(méi)有明說(shuō)這件事啊？只看到兩三篇是這個(gè)意思的（這個(gè)和這個(gè)，yyb的其實(shí)也是吧），其它題解只是寫(xiě)了下\(s\)的定義，一點(diǎn)關(guān)于"左右端點(diǎn)選不選"是什么的解釋都沒(méi)有（當(dāng)然也許只是我不能理解）。
當(dāng)然只是個(gè)人理解咯。（表示我一共想了三種理解哪種都能和代碼對(duì)應(yīng)上，但前兩種并不能說(shuō)過(guò)去）

然后，小區(qū)間內(nèi)部的答案在合并成大區(qū)間時(shí)是不會(huì)變的，要考慮的只是端點(diǎn)屬于哪個(gè)區(qū)間的問(wèn)題。
所以可以用線段樹(shù)維護(hù)，令\(L,R\)表示當(dāng)前區(qū)間的\(B_l,B_r\)，\(s_0,s_1,s_2,s_3\)分別表示，左右端點(diǎn)都不屬于這個(gè)區(qū)間（不與這個(gè)區(qū)間中的數(shù)構(gòu)成等差數(shù)列）時(shí)的答案， 左端點(diǎn)屬于而右端點(diǎn)不屬于這個(gè)區(qū)間的答案，右端點(diǎn)屬于而左端點(diǎn)不屬于這個(gè)區(qū)間的答案，左右端點(diǎn)都屬于這個(gè)區(qū)間的答案。
有這些就可以合并區(qū)間了，這里就可以見(jiàn)代碼了。
詢問(wèn)的答案，就是詢問(wèn)區(qū)間合并后的\(s_3\)。
因?yàn)槭窃诓罘趾蟮男蛄猩献?#xff0c;詢問(wèn)\([l,r]\)是查詢\([l,r-1]\)，還要注意邊界問(wèn)題。
復(fù)雜度\(O(q\log n)\)。

//12460kb   2476ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5;int A[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Node
{int L,R,s0,s1,s2,s3;//s0:(l,r) 左右都不屬于 s1:[l,r) s2:(l,r] s3:[l,r] inline Node operator +(const Node &b){Node c;c.L=L, c.R=b.R; int v=R==b.L;c.s0=std::min(s2+b.s1-v, std::min(s0+b.s1, s2+b.s0));c.s1=std::min(s3+b.s1-v, std::min(s3+b.s0, s1+b.s1));c.s2=std::min(s2+b.s3-v, std::min(s0+b.s3, s2+b.s2));c.s3=std::min(s3+b.s3-v, std::min(s1+b.s3, s3+b.s2));return c;}
};
struct Segment_Tree
{#define ls rt<<1#define rs rt<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define S N<<2int tag[S];Node t[S];#undef S#define Upd(x,v) t[x].L+=v, t[x].R+=v, tag[x]+=v#define Update(rt) t[rt]=t[ls]+t[rs]inline void PushDown(int rt){Upd(ls,tag[rt]), Upd(rs,tag[rt]), tag[rt]=0;}void Build(int l,int r,int rt){if(l==r){t[rt]=(Node){A[l],A[l],0,1,1,1};return;}int m=l+r>>1;Build(lson), Build(rson), Update(rt);}void Modify(int l,int r,int rt,int L,int R,int v){if(L<=l && r<=R) {Upd(rt,v); return;}if(tag[rt]) PushDown(rt);int m=l+r>>1;if(L<=m) Modify(lson,L,R,v);if(m<R) Modify(rson,L,R,v);Update(rt);}void ModifyP(int l,int r,int rt,int p,int v){if(l==r) {Upd(rt,v); return;}if(tag[rt]) PushDown(rt);int m=l+r>>1;p<=m ? ModifyP(lson,p,v) : ModifyP(rson,p,v);Update(rt);}Node Query(int l,int r,int rt,int L,int R){if(L<=l && r<=R) return t[rt];if(tag[rt]) PushDown(rt);int m=l+r>>1;if(L<=m)if(m<R) return Query(lson,L,R)+Query(rson,L,R);else return Query(lson,L,R);return Query(rson,L,R);}
}T;inline int read()
{int now=0,f=1;register char c=gc();for(;!isdigit(c);c=='-'&&(f=-1),c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now*f;
}
inline char GetOpt()
{register char c=gc();while(c!='A'&&c!='B') c=gc();return c;
}int main()
{int n=read();for(int i=1; i<=n; ++i) A[i]=read();if(n==1){for(int Q=read(); Q--; )if(GetOpt()=='B') puts("1");return 0;}--n;for(int i=1; i<=n; ++i) A[i]=A[i+1]-A[i];T.Build(1,n,1);for(int Q=read(); Q--; )switch(GetOpt()){case 'A':{int l=read(),r=read(),a=read(),d=read();if(l<r) T.Modify(1,n,1,l,r-1,d);if(l>1) T.ModifyP(1,n,1,l-1,a);if(r<=n) T.ModifyP(1,n,1,r,(l-r)*d-a);//r!=n!break;}case 'B':{int l=read(),r=read();if(l!=r) printf("%d\n",T.Query(1,n,1,l,r-1).s3);else puts("1");break;}}return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/10271976.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ.1558.[JSOI2009]等差数列(线段树 差分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。