第一篇博客哒

题目链接

首先看到区间加等差数列我们可以首先想到使用差分数组

就是记一个\(b_i\)=\(a_{i+1}\)-\(a_i\)

然后每次修改\(a_l\) 到\(a_r\)就只用将\(b_{l-1}\),\(b_r\)单点修改,\(b_l\)至\(b_{r-1}\)区间修改就可以了

区间修改？我们首先想到了线段树

线段树可以维护是否为等差数列吗？？？

可以！

每个结点维护上啥线段树必要的l,r,lazy标记什么的在多维护一个结构体val

val 里面有什么呢？

首先为了下面转移方便维护区间最左边lv，最右边的点的值rv

然后维护ls,rs,nos,lrs

分别表示[l,r) (l,r] (l,r) [l,r] 区间的答案

开始转移 我们考虑合并区间a,和区间b

考虑\(a_r\) \(b_l\)这两个点

有以下三种情况

1.可以直接合并。如果两者的差值相同，则可以将原来的等差数列合并为一个 2.a两侧都不选，左边的右端点作为一个等差数列的首项(所以不选)，b就要选择左端点(因为他不用考虑做首项了) 3.a选右端点，，b的左端点作为一个等差数列的首项，所以b两边都不选

如何操作，看代码吧

#include<cstdio> inline int min(int a,int b){return a<b?a:b;} inline int m(int a,int b,int c ){return min(a,min(b,c));} using namespace std; const int N=400100; int a[N],n,q,x,y,s,b; char opt[10]; struct val{int ls,lv,rv,rs,lrs,nos;}; struct seg{int l,r,tag;val s;}t[N]; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; } val operator+(val l,val r) { val x; x.lv=l.lv, x.rv=r.rv; x.ls=m(l.lrs+r.ls-(l.rv==r.lv),l.lrs+r.nos,l.ls+r.ls); x.rs=m(l.rs+r.lrs-(l.rv==r.lv),l.rs+r.rs,l.nos+r.lrs); x.nos=m(l.rs+r.ls-(l.rv==r.lv),l.rs+r.nos,l.nos+r.ls); x.lrs=m(l.lrs+r.lrs-(l.rv==r.lv),l.lrs+r.rs,l.ls+r.lrs); return x; } inline void build(int pos,int l,int r) { t[pos].l=l,t[pos].r=r; if(l==r) { t[pos].s.lv=t[pos].s.rv=a[l]; t[pos].s.ls=t[pos].s.rs=t[pos].s.lrs=1;return ; } int mid=l+r>>1; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); t[pos].s=t[pos<<1].s+t[pos<<1|1].s; } inline void pushdown(int pos) { int tag=t[pos].tag; if(tag) { t[pos].tag=0; t[pos<<1].s.lv+=tag,t[pos<<1|1].s.lv+=tag; t[pos<<1].tag+=tag, t[pos<<1|1].tag+=tag; t[pos<<1].s.rv+=tag,t[pos<<1|1].s.rv+=tag; } } inline void modify(int pos,int x,int y,int w) { if(x<=t[pos].l&&t[pos].r<=y) { t[pos].tag+=w,t[pos].s.lv+=w,t[pos].s.rv+=w; return ; } pushdown(pos); int mid=t[pos].l+t[pos].r>>1; if(y<=mid) modify(pos<<1,x,y,w); else if(x>mid) modify(pos<<1|1,x,y,w); else modify(pos<<1,x,y,w),modify(pos<<1|1,x,y,w); t[pos].s=t[pos<<1].s+t[pos<<1|1].s; } inline val query(int pos,int x,int y) { if(x<=t[pos].l&&t[pos].r<=y) return t[pos].s; int mid=t[pos].l+t[pos].r>>1; pushdown(pos); if(y<=mid) return query(pos<<1,x,y); if(x>mid) return query(pos<<1|1,x,y); return query(pos<<1,x,y)+query(pos<<1|1,x,y); } int main() { read(n); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<n;i++) a[i]=a[i+1]-a[i]; build(1,1,n-1); read(q); for(int i=1;i<=q;i++) { scanf("%s",opt); if(opt[0]=='A') { read(x),read(y),read(s),read(b); if(x!=1) modify(1,x-1,x-1,s); if(x!=y) modify(1,x,y-1,b); if(y!=n) modify(1,y,y,-((y-x)*b+s)); } else { read(x),read(y); if(x==y) puts("1"); else printf("%d\n",query(1,x,y-1).lrs); } } }

　　

[JSOI2009]等差数列