[JSOI2009]等差数列

模拟赛开始时正在做这道原题。。。

传送门

首先加等差序列肯定要想到差分，我们可以维护原数列的差分数组。如果其有一连串相同的数字，那么就可以形成一个等差数列。

这是一个比较粗糙的想法，我们来看一个例子。

假如有一个差分数组：1 1 1 2 3 3

它的原数组是：0 1 2 3 5 8 11

按我们之前的想法是分成0 1 2 3、5和8 11。

但实际上可以分成0 1 2 3和5 8 11

原因是2可以和后面一段3合起来，因为2是5和3的差。

那么我们还要考虑一段数带上另一个数的情况。

所以线段树除了要维护区间左右数字还要维护一个区间左右端点取或不取的答案。

转移的时候

sum[rt][0][0]=min(sum[rt<<1][0][1]+sum[rt<<1|1][1][0]-o,
          min(sum[rt<<1][0][0]+sum[rt<<1|1][1][0],
          sum[rt<<1][0][1]+sum[rt<<1|1][0][0]));
sum[rt][0][1]=min(sum[rt<<1][0][1]+sum[rt<<1|1][1][1]-o,
          min(sum[rt<<1][0][0]+sum[rt<<1|1][1][1],
          sum[rt<<1][0][1]+sum[rt<<1|1][0][1]));
sum[rt][1][0]=min(sum[rt<<1][1][1]+sum[rt<<1|1][1][0]-o,
          min(sum[rt<<1][1][0]+sum[rt<<1|1][1][0],
          sum[rt<<1][1][1]+sum[rt<<1|1][0][0]));
sum[rt][1][1]=min(sum[rt<<1][1][1]+sum[rt<<1|1][1][1]-o,
          min(sum[rt<<1][1][0]+sum[rt<<1|1][1][1],
          sum[rt<<1][1][1]+sum[rt<<1|1][0][1]));

意思是区间中间可以有一个点不取，和后面的颜色段构成等差，但不能两个都不取。

完整代码：

#include<cstdio>
#include<iostream>
using namespace std;
int sum[400001][2][2],lazy[400001],t;
int ls[400001],rs[400001],a[100001],n;
inline void pushup(int rt){
    ls[rt]=ls[rt<<1]; rs[rt]=rs[rt<<1|1];
    int o=(rs[rt<<1]==ls[rt<<1|1]);
    sum[rt][0][0]=min(sum[rt<<1][0][1]+sum[rt<<1|1][1][0]-o,
              min(sum[rt<<1][0][0]+sum[rt<<1|1][1][0],
              sum[rt<<1][0][1]+sum[rt<<1|1][0][0]));
    sum[rt][0][1]=min(sum[rt<<1][0][1]+sum[rt<<1|1][1][1]-o,
              min(sum[rt<<1][0][0]+sum[rt<<1|1][1][1],
              sum[rt<<1][0][1]+sum[rt<<1|1][0][1]));
    sum[rt][1][0]=min(sum[rt<<1][1][1]+sum[rt<<1|1][1][0]-o,
              min(sum[rt<<1][1][0]+sum[rt<<1|1][1][0],
              sum[rt<<1][1][1]+sum[rt<<1|1][0][0]));
    sum[rt][1][1]=min(sum[rt<<1][1][1]+sum[rt<<1|1][1][1]-o,
              min(sum[rt<<1][1][0]+sum[rt<<1|1][1][1],
              sum[rt<<1][1][1]+sum[rt<<1|1][0][1]));
}
void build(int rt,int l,int r){
    if (l==r){
        sum[rt][0][0]=0; ls[rt]=rs[rt]=a[l];
        sum[rt][0][1]=sum[rt][1][0]=sum[rt][1][1]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
inline void pushdown(int rt){
    if (!lazy[rt]) return;
    ls[rt<<1]+=lazy[rt]; rs[rt<<1]+=lazy[rt];
    ls[rt<<1|1]+=lazy[rt]; rs[rt<<1|1]+=lazy[rt];
    lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt];
    lazy[rt]=0;
}
void update(int rt,int l,int r,int x,int y,int z){
    if (x>y) return;
    if (x<=l&&r<=y){
        lazy[rt]+=z;
        ls[rt]+=z; rs[rt]+=z;
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if (x<=mid) update(rt<<1,l,mid,x,y,z);
    if (y>mid) update(rt<<1|1,mid+1,r,x,y,z);
    pushup(rt);
}
struct node{
    int ls,rs,sum[2][2];
};
inline node unionn(node a,node b){
    // if (a.sum[0][0]!=n+1){
        node c;
        c.ls=a.ls; c.rs=b.rs;
        int o=(a.rs==b.ls);
        c.sum[0][0]=min(a.sum[0][1]+b.sum[1][0]-o,
                min(a.sum[0][0]+b.sum[1][0],
                a.sum[0][1]+b.sum[0][0]));
        c.sum[0][1]=min(a.sum[0][1]+b.sum[1][1]-o,
                min(a.sum[0][0]+b.sum[1][1],
                a.sum[0][1]+b.sum[0][1]));
        c.sum[1][0]=min(a.sum[1][1]+b.sum[1][0]-o,
                min(a.sum[1][0]+b.sum[1][0],
                a.sum[1][1]+b.sum[0][0]));
        c.sum[1][1]=min(a.sum[1][1]+b.sum[1][1]-o,
                min(a.sum[1][0]+b.sum[1][1],
                a.sum[1][1]+b.sum[0][1]));
        return c;
    // }
    // return b;
}
node query(int rt,int l,int r,int x,int y){
    if (x<=l&&r<=y){
        node ans;
        ans.ls=ls[rt],ans.rs=rs[rt];
        ans.sum[0][0]=sum[rt][0][0];
        ans.sum[0][1]=sum[rt][0][1];
        ans.sum[1][0]=sum[rt][1][0];
        ans.sum[1][1]=sum[rt][1][1];
        return ans;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if (y<=mid) return query(rt<<1,l,mid,x,y);
    if (x>mid) return query(rt<<1|1,mid+1,r,x,y);
    return unionn(query(rt<<1,l,mid,x,mid),query(rt<<1|1,mid+1,r,mid+1,y));
    // if (x<=mid) ans=unionn(ans,query(rt<<1,l,mid,x,y));
    // if (y>mid) ans=unionn(ans,query(rt<<1|1,mid+1,r,x,y));
    // return ans;
}
int main(){
    int x,y,l,r;char ch[5];
    scanf("%d",&n);
    scanf("%d",&y);
    for (int i=2; i<=n; i++){
        scanf("%d",&x);
        a[i-1]=x-y; y=x;
    }
    build(1,1,n-1);
    scanf("%d",&t);
    while (t--){
        scanf("%s",ch);
        if (ch[0]=='A'){
            scanf("%d%d%d%d",&l,&r,&x,&y);
            if (l>1) update(1,1,n-1,l-1,l-1,x);
            if (l<r) update(1,1,n-1,l,r-1,y);
            if (r<n) update(1,1,n-1,r,r,-x-(r-l)*y);
        }
        else{
            scanf("%d%d",&x,&y);
            if (x==y){puts("1"); continue;}
            node ans=query(1,1,n-1,x,y-1);
            printf("%d\n",ans.sum[1][1]);
        }
    }
    return 0;
}