P4243 [JSOI2009]等差数列

P4243 [JSOI2009]等差数列
这个题可以用差分做
因为等差数列的性质就是差相等
我们维护这些东西
当前区间的左端点的数值 ->vl
当前区间的右端点的数值 -> vr
当前区间如果左右端点都不选有多少个等差数列 -> s[0]
当前区间如果只选左端点有多少个等差数列 -> s[1]
当前区间如果只选右端点有多少个等差数列 -> s[2]
当前区间如果左右端点都选有多少个等差数列 -> s[3]
就会发现
区间可以这么合并

$$vl[o]=vl[l];vr[o]=vr[r];$$
$$s[o][0]=minn(s[l][1]+s[r][2]-(vr[l]==vl[r]),s[l][0]+s[r][2],s[r][0]+s[l][1]);$$
$$s[o][1]=minn(s[l][1]+s[r][3]-(vr[l]==vl[r]),s[l][0]+s[r][3],s[r][1]+s[l][1]);$$
$$s[o][2]=minn(s[l][3]+s[r][2]-(vr[l]==vl[r]),s[l][3]+s[r][0],s[r][2]+s[l][2]);$$
$$s[o][3]=minn(s[l][3]+s[r][3]-(vr[l]==vl[r]),s[l][2]+s[r][3],s[r][1]+s[l][3]);$$
就OK了
查询时要多开些点，保留合并的信息

#include<cstdio>
#include<iostream>
#define ls o<<1 
#define rs o<<1|1 
using namespace std;
const int M=1000000;
int n,q,a[M],cnt,maxn;
struct SIG{int vl[4*M],vr[4*M],s[4*M][4],add[4*M];int minn(int y,int z,int w){return min(min(w,y),z);}void update(int o,int l,int r){vl[o]=vl[l];vr[o]=vr[r];s[o][0]=minn(s[l][1]+s[r][2]-(vr[l]==vl[r]),s[l][0]+s[r][2],s[r][0]+s[l][1]);s[o][1]=minn(s[l][1]+s[r][3]-(vr[l]==vl[r]),s[l][0]+s[r][3],s[r][1]+s[l][1]);s[o][2]=minn(s[l][3]+s[r][2]-(vr[l]==vl[r]),s[l][3]+s[r][0],s[r][2]+s[l][2]);s[o][3]=minn(s[l][3]+s[r][3]-(vr[l]==vl[r]),s[l][2]+s[r][3],s[r][1]+s[l][3]);}void built(int o,int l,int r){if(l==r) {vl[o]=a[l];vr[o]=a[l];add[o]=0;s[o][1]=s[o][2]=s[o][3]=1;s[o][0]=0;return ;}int mid=(l+r)>>1;built(ls,l,mid);built(rs,mid+1,r);cnt=max(cnt,rs);maxn=cnt;add[o]=0;update(o,ls,rs);}void pushdown(int o){if(add[o]){add[ls]+=add[o];add[rs]+=add[o];vl[ls]+=add[o];vl[rs]+=add[o];vr[ls]+=add[o];vr[rs]+=add[o];add[o]=0;}}void modify(int o,int l,int r,int ql,int qr,int ins){if(l>qr||r<ql) return ;if(l>=ql&&r<=qr) {vl[o]+=ins;vr[o]+=ins;add[o]+=ins; return ;} pushdown(o);int mid=(l+r)>>1;modify(ls,l,mid,ql,qr,ins);modify(rs,mid+1,r,ql,qr,ins);update(o,ls,rs);}int query(int o,int l,int r,int ql,int qr){if(l>qr||r<ql) return 0;if(l>=ql&&r<=qr)   return o;int mid=(l+r)>>1;pushdown(o);int t1=query(ls,l,mid,ql,qr);int t2=query(rs,mid+1,r,ql,qr);if(t1&&t2)update(++cnt,t1,t2);if(t1&&t2) return cnt;else return t1?t1:t2; }
}T;
int main(){scanf("%d",&n);cnt=n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++) a[i]=a[i+1]-a[i];T.built(1,1,n-1);scanf("%d",&q);while(q--){char s[10];int l,r,x,y;scanf("%s%d%d",s,&l,&r);if(s[0]=='A'){scanf("%d%d",&x,&y);if(l!=1) T.modify(1,1,n-1,l-1,l-1,x);if(r!=n) T.modify(1,1,n-1,r,r,-(x+y*(r-l)));if(l!=r) T.modify(1,1,n-1,l,r-1,y);}else{
   if(l==r) puts("1");else cnt=maxn,printf("%d\n",T.s[T.query(1,1,n-1,l,r-1)][3]);}}
}