[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)

发布于 2018-04-17  49 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)

Description

BZOJ1558

Tag

线段树,差分

解决思路

一般而言,遇到等差数列的问题,通常是转化为差分数组后,相同的数即可组成一个等差数列。
但,等差数列差分后,第一个数是可以与后面的数不一样的,这就不是很好处理。所以,要把它们分开考虑。
具体来说,用线段树维护区间左右端点的值,然后再维护f00,f01,f10,f11分别表示前后端点选or不选时的最小等差数列个数,0代表不选,1代表选。这里的选指的是是否记录进当前区间的答案。
那么合并两个区间的时候,分情况讨论一下求和。
至于修改,考虑差分后的数组,则是两个端点的单点修改和中间区间的区间修改操作。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)
#define MIN(a,b,c) min(a,min(b,c))

const int maxN=101000;
const int inf=2147483647;

class Data
{
public:
    int f00,f01,f10,f11;
    int left,right;
    int lazy;
    Data(){
        lazy=0;
    }
};

int n,m;
int Arr[maxN];
Data S[maxN<<2];

Data operator + (Data A,Data B);
void PushDown(int now);
void Build(int now,int l,int r);
void Modify(int now,int l,int r,int ql,int qr,int key);
Data Query(int now,int l,int r,int ql,int qr);
void OutpNum(int now,int l,int r);

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&Arr[i]);
    for (int i=n;i>=1;i--) Arr[i]=Arr[i]-Arr[i-1];
    Build(1,1,n);

    cin>>m;
    while (m--)
    {
        char opt;
        opt=getchar();
        while ((opt!='A')&&(opt!='B')) opt=getchar();
        if (opt=='A')
        {
            int s,t,a,b;scanf("%d%d%d%d",&s,&t,&a,&b);
            Modify(1,1,n,s,s,a);//单点修改left
            if (s<t) Modify(1,1,n,s+1,t,b);//区间修改
            if (t<n) Modify(1,1,n,t+1,t+1,-(t-s)*b-a);//单点修改right+1
        }
        if (opt=='B')
        {
            int s,t;scanf("%d%d",&s,&t);
            Data G=Query(1,1,n,s,t);
            printf("%d\n",min(G.f11,G.f01));//注意这里只能是头尾都选或头不选
        }
    }
    return 0;
}

Data operator + (Data A,Data B)//分情况讨论,合并答案
{
    Data Ret;
    Ret.left=A.left;Ret.right=B.right;
    Ret.f00=MIN(A.f01+B.f10-(A.right==B.left),A.f00+B.f10,A.f01+B.f00);
    Ret.f01=MIN(A.f01+B.f11-(A.right==B.left),A.f00+B.f11,A.f01+B.f01);
    Ret.f10=MIN(A.f11+B.f10-(A.right==B.left),A.f10+B.f10,A.f11+B.f00);
    Ret.f11=MIN(A.f11+B.f11-(A.right==B.left),A.f10+B.f11,A.f11+B.f01);
    return Ret;
}

void PushDown(int now)
{
    if (S[now].lazy)
    {
        int lz=S[now].lazy;
        S[lson].left+=lz;S[lson].right+=lz;S[lson].lazy+=lz;
        S[rson].left+=lz;S[rson].right+=lz;S[rson].lazy+=lz;
        S[now].lazy=0;
    }
    return;
}

void Build(int now,int l,int r)
{
    if (l==r)
    {
        S[now].f00=0;S[now].f10=S[now].f01=1;S[now].f11=1;
        S[now].left=S[now].right=Arr[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(lson,l,mid);Build(rson,mid+1,r);
    S[now]=S[lson]+S[rson];
    return;
}

void Modify(int now,int l,int r,int ql,int qr,int key)
{
    if ((l==ql)&&(r==qr))
    {
        S[now].left+=key;S[now].right+=key;S[now].lazy+=key;
        return;
    }
    PushDown(now);
    int mid=(l+r)>>1;
    if (qr<=mid) Modify(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify(lson,l,mid,ql,mid,key);
        Modify(rson,mid+1,r,mid+1,qr,key);
    }
    S[now]=S[lson]+S[rson];
    return;
}

Data Query(int now,int l,int r,int ql,int qr)
{
    if ((l==ql)&&(r==qr)) return S[now];
    PushDown(now);
    int mid=(l+r)>>1;
    if (qr<=mid) return Query(lson,l,mid,ql,qr);
    else if (ql>=mid+1) return Query(rson,mid+1,r,ql,qr);
    else return Query(lson,l,mid,ql,mid)+Query(rson,mid+1,r,mid+1,qr);
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)


HNCJ OIer 一枚