Description
Solution
把原数组变为差分数组,然后剩下的就十分显然了
区间查询用线段树维护
修改操作就是区间加法和两个单点修改
一个等差数列实际上就是 开头一个数字+数值相等的一段
唯一的难点在于讨论这个开头的数字的去向
在线段树合并的时候
\(mid\) 左右两个元素如果相等的话是可以合并的,所以还需要做讨论
所以我们可以先不把左右两端点列入考虑对象,然后在合并时再讨论去向,综上需要维护的东西有:
1.区间的左右两个端点都不列入考虑的等差数列数量
2.区间的左端点列入考虑
3.区间的右段点列入考虑
4.区间的左右端点都列入考虑
\(4\) 就是我们要求的,每一种情况的转移都是类似的,转移我们可以分三种情况讨论:
1.左边的右端点和右边的左端点本身作为了等差数列的开头,左边的和右边的等差数列直接合并,如果相邻元素相等,则合为一个等差数列
2.左边的右端点自成一个等差数列
3.右边的左端点自成一个等差数列
#include<bits/stdc++.h>#define ls (o<<1)#define rs (o<<1|1)using namespace std;const int N=1e5+10;int n,Q,a[N],w[N],la[N*4];struct sub{ ???int a[4],wl,wr;}t[N*4];inline sub upd(sub a,sub b){ ???sub c; ???c.a[0]=min(a.a[2]+b.a[1]-(a.wr==b.wl),min(a.a[0]+b.a[1],a.a[2]+b.a[0])); ???c.a[1]=min(a.a[3]+b.a[1]-(a.wr==b.wl),min(a.a[1]+b.a[1],a.a[3]+b.a[0])); ???c.a[2]=min(a.a[2]+b.a[3]-(a.wr==b.wl),min(a.a[2]+b.a[2],a.a[0]+b.a[3])); ???c.a[3]=min(a.a[3]+b.a[3]-(a.wr==b.wl),min(a.a[3]+b.a[2],a.a[1]+b.a[3])); ???c.wl=a.wl;c.wr=b.wr; ???return c;}inline void build(int l,int r,int o){ ???if(l==r){ ???????t[o].wl=t[o].wr=w[l]; ???????t[o].a[1]=t[o].a[2]=t[o].a[3]=1;t[o].a[0]=0; ???????return ; ???} ???int mid=(l+r)>>1; ???build(l,mid,ls);build(mid+1,r,rs); ???t[o]=upd(t[ls],t[rs]);}inline void pushdown(int o){ ???if(!la[o])return ; ???int k=la[o];la[o]=0; ???t[ls].wl+=k;t[ls].wr+=k;la[ls]+=k; ???t[rs].wl+=k;t[rs].wr+=k;la[rs]+=k;}inline sub qry(int l,int r,int o,int sa,int se){ ???if(sa<=l && r<=se)return t[o]; ???int mid=(l+r)>>1;sub ret; ???pushdown(o); ???if(se<=mid)ret=qry(l,mid,ls,sa,se); ???else if(sa>mid)ret=qry(mid+1,r,rs,sa,se); ???else ret=upd(qry(l,mid,ls,sa,mid),qry(mid+1,r,rs,mid+1,se)); ???t[o]=upd(t[ls],t[rs]); ???return ret;}inline void Modify(int l,int r,int o,int sa,int se,int z){ ???if(sa<=l && r<=se){ ???????la[o]+=z;t[o].wl+=z;t[o].wr+=z; ???????return ; ???} ???pushdown(o); ???int mid=(l+r)>>1; ???if(se<=mid)Modify(l,mid,ls,sa,se,z); ???else if(sa>mid)Modify(mid+1,r,rs,sa,se,z); ???else Modify(l,mid,ls,sa,mid,z),Modify(mid+1,r,rs,mid+1,se,z); ???t[o]=upd(t[ls],t[rs]);}int main(){ ?freopen("pp.in","r",stdin); ?freopen("pp.out","w",stdout); ?scanf("%d",&n); ?for(int i=1;i<=n;i++)scanf("%d",&a[i]); ?for(int i=1;i<n;i++)w[i]=a[i+1]-a[i]; ?build(1,n-1,1); ?int x,y,p,q;char op[3]; ?scanf("%d",&Q); ?while(Q--){ ?????scanf("%s%d%d",op,&x,&y); ?????if(op[0]=='B'){ ?????????if(x==y)puts("1"); ?????????else printf("%d\n",qry(1,n-1,1,x,y-1).a[3]); ?????} ?????else{ ?????????scanf("%d%d",&p,&q); ?????????if(x>1)Modify(1,n-1,1,x-1,x-1,p); ?????????if(y<n)Modify(1,n-1,1,y,y,-p-(y-x)*q); ?????????if(x<y)Modify(1,n-1,1,x,y-1,q); ?????} ?} ?return 0;}bzoj 1558: [JSOI2009]等差数列
原文地址：https://www.cnblogs.com/Yuzao/p/8586159.html