题解 P4243 【[JSOI2009]等差数列】
alpq010815 · · 题解
这个题可以用差分做 因为等差数列的性质就是差相等 我们维护这些东西
当前区间的右端点的数值 -> 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了
查询时要多开些点，保留合并的信息
没加读优跑了6000ms，开o2跑了2000ms
还算可以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[4M],vr[4M],s[4M][4],add[4M]; 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]); } } }