題目鏈接：戳我

實話實話，看了幾篇題解真的沒看懂，我覺得講的都有問題。這里對于線段樹維護的s寫了一點我自己的理解。

看到等差數列，我們考慮對數列做差，這樣如果是等差數列，那么值應該相等。（比較容易維護，修改操作就變成了兩個單點修改+一個區間修改，如果還是不理解的話可以參考一下代碼）

查詢比較麻煩，有這樣的情況需要考慮：

舉個例子——
1 3 5 6 9 12
它的差分數列為 2 2 1 3 3

最佳選擇肯定是（1,3,5）（6,9,12），ans=2
但是我們純看差分數列找相同的，ans=3

為什么會多算呢？原因就在于差分數列為1的這個位置其實是兩個等差數列拼合點，不需要考慮在內。

所以我們設\(s[0],s[1],s[2],s[3]\)分別表示當前區間中，不考慮兩端、不考慮左端點、不考慮右端點、兩端都考慮，形成等差數列的個數。

兩個區間合并的時候，左區間的右端點和右區間的左端點是至少要考慮一個的。因為如果都不考慮的娿，終究就遺漏了一個點了。兩個都考慮時，如果中間差值相同，那么兩個等差數列可以拼做一個，ans要-1.

注意查詢的時候區間寫（l,r-1）qwqwqwq

備注一下l,r記錄的是左右端點的數值。

代碼如下：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; #define MAXN 120000 int v[MAXN],n; struct Data{int s[4],l,r;}; struct Node {int l,r,v;Data x; }t[MAXN<<2];Data operator + (Data x,Data y) {Data cur;cur.l=x.l,cur.r=y.r;cur.s[0]=min(x.s[2]+y.s[0],x.s[0]+y.s[1]);cur.s[0]=min(cur.s[0],x.s[2]+y.s[1]-(y.l==x.r));cur.s[1]=min(x.s[1]+y.s[1],x.s[3]+y.s[0]);cur.s[1]=min(cur.s[1],x.s[3]+y.s[1]-(y.l==x.r));cur.s[2]=min(x.s[2]+y.s[2],x.s[0]+y.s[3]);cur.s[2]=min(cur.s[2],x.s[2]+y.s[3]-(y.l==x.r));cur.s[3]=min(x.s[3]+y.s[2],x.s[1]+y.s[3]);cur.s[3]=min(cur.s[3],x.s[3]+y.s[3]-(y.l==x.r));return cur; }inline int ls(int x){return x<<1;}inline int rs(int x){return x<<1|1;}inline void solve(int now,int k) {t[now].v+=k;t[now].x.l+=k;t[now].x.r+=k; } inline void pushdown(int now) {if(t[now].v){solve(ls(now),t[now].v);solve(rs(now),t[now].v);t[now].v=0;} }inline void Build(int now,int l,int r) {t[now].l=l,t[now].r=r;if(l==r){t[now].x.s[0]=0;t[now].x.s[1]=t[now].x.s[2]=t[now].x.s[3]=1;t[now].x.l=t[now].x.r=v[l];return;}int mid=(l+r)>>1;Build(ls(now),l,mid);Build(rs(now),mid+1,r);t[now].x=t[ls(now)].x+t[rs(now)].x; }inline Data Query(int now,int ll,int rr) {int l=t[now].l,r=t[now].r;if(l==ll&&r==rr) return t[now].x;pushdown(now);int mid=(l+r)>>1;if(rr<=mid) return Query(ls(now),ll,rr);if(mid<ll) return Query(rs(now),ll,rr);return Query(ls(now),ll,mid)+Query(rs(now),mid+1,rr); }inline void Modify(int now,int ll,int rr,int k) {int L=t[now].l,R=t[now].r;if(L==ll&&R==rr){t[now].v+=k;t[now].x.l+=k,t[now].x.r+=k;return;}pushdown(now);int mid=(L+R)>>1;if(rr<=mid) Modify(ls(now),ll,rr,k);else if(mid<ll) Modify(rs(now),ll,rr,k);else{Modify(ls(now),ll,mid,k);Modify(rs(now),mid+1,rr,k);}t[now].x=t[ls(now)].x+t[rs(now)].x; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);freopen("std.out","w",stdout);#endif scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&v[i]);for(int i=1;i<n;i++) v[i]=v[i+1]-v[i];Build(1,1,n-1);int Q;scanf("%d",&Q);for(int i=1;i<=Q;i++){char op[10];int s,t,a,b;scanf("%s",op);if(op[0]=='B'){scanf("%d%d",&s,&t);if(s==t) printf("1\n");else printf("%d\n",Query(1,s,t-1).s[3]);}else if(op[0]=='A') {scanf("%d%d%d%d",&s,&t,&a,&b);if(s!=1) Modify(1,s-1,s-1,a); if(s!=t) Modify(1,s,t-1,b);if(t!=n) Modify(1,t,t,-(t-s)*b-a); }}return 0; }

轉載于:https://www.cnblogs.com/fengxunling/p/10501139.html

總結

以上是生活随笔為你收集整理的BZOJ1558 等差数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。