[JSOI2009]等差数列

链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1558

题解：

考虑这么用线段树进行维护，由于他有区间修改等差数列

很容易想到可以用差分数组来维护（这东西经常和数据结构用在一起）

那么每一次的区间修改就变成了单点修改

另外我们可以利用线段树来维护：

h---t区间等差数列个数，h----（t-1）区间等差数列个数，（h+1）---t区间等差数列个数

为了维护这三个值，要引入(h+1)-----（t-1）（这个转移非常巧妙）

为什么要维护这些呢，因为我们算一个就可以发现

当他们不是一个等差数列时，区间中有一个数是没有用的

由于进行了差分，等差数列其实就是差分数组的值相同

bzoj re了并不知道为什么对拍是对的

代码：

#include <bits/stdc++.h>

#define maxn 311111

#define mid (p[x].h+p[x].t)/2

using namespace std;

int n,m,a[maxn*],b[maxn*];

struct re

{

    int h,t,sum,sum1,sum2,sum3,lazy,hnum,tnum;

}p[maxn*];

struct ree

{

    int sum,sum1,sum2;

};

void updata(int x)

{

    p[x].sum=min(p[x*].sum2+p[x*+].sum,p[x*].sum+p[x*+].sum1);

    p[x].sum1=min(p[x*].sum3+p[x*+].sum,p[x*].sum1+p[x*+].sum1);

    p[x].sum2=min(p[x*].sum2+p[x*+].sum2,p[x*].sum+p[x*+].sum3);

    p[x].sum3=min(p[x*].sum3+p[x*+].sum2,p[x*].sum1+p[x*+].sum3);

    if (p[x*].tnum==p[x*+].hnum)

    {

        p[x].sum=min(p[x].sum,p[x*].sum+p[x*+].sum-);

        p[x].sum1=min(p[x].sum1,p[x*].sum1+p[x*+].sum-);

        p[x].sum2=min(p[x].sum2,p[x*].sum+p[x*+].sum2-);

        p[x].sum3=min(p[x].sum3,p[x*].sum1+p[x*+].sum2-);

    }

}

void build(int x,int h,int t)

{

    p[x].h=h; p[x].t=t;

    p[x].hnum=b[p[x].h];

    p[x].tnum=b[p[x].t];

    if (p[x].h==p[x].t)

    {

        p[x].sum=p[x].sum1=p[x].sum2=;p[x].sum3=; return;

    }

    build(x*,h,mid); build(x*+,mid+,t);

    updata(x);

}

void down(int x)

{

  if (p[x].lazy)

  {

     p[x].hnum+=p[x].lazy;

     p[x].tnum+=p[x].lazy;

     if (p[x].h!=p[x].t)

     {

         p[x*].lazy+=p[x].lazy;

         p[x*+].lazy+=p[x].lazy;

     }

     p[x].lazy=;

  }

}

void change(int x,int h,int t,int sum)

{

    down(x);

    if (p[x].h>t||p[x].t<h) return;

    if (h<=p[x].h&&p[x].t<=t)

    {

        p[x].lazy+=sum; down(x);

        return;

    }

    if (p[x].h<=t&&p[x].h>=h) p[x].hnum+=sum;

    if (p[x].t<=t&&p[x].t>=h) p[x].tnum+=sum;

    change(x*,h,t,sum);

    change(x*+,h,t,sum);

    updata(x);

}

re query(int x,int h,int t)

{

    down(x);

    re now;

    if (h<=p[x].h&&p[x].t<=t)

    {

      now=p[x];

      return(now);

    }

    if (mid+>t) return(query(x*,h,t));

    if (mid<h) return(query(x*+,h,t));

    re a=query(x*,h,t),b=query(x*+,h,t);

    now.sum=min(a.sum2+b.sum,a.sum+b.sum1);

    now.sum1=min(a.sum3+b.sum,a.sum1+b.sum1);

    now.sum2=min(a.sum2+b.sum2,a.sum+b.sum3);

    now.sum3=min(a.sum3+b.sum2,a.sum1+b.sum3);

    if (p[x*].tnum==p[x*+].hnum)

    {

        now.sum=min(now.sum,a.sum+b.sum-);

        now.sum1=min(now.sum1,a.sum1+b.sum-);

        now.sum2=min(now.sum2,a.sum+b.sum2-);

        now.sum3=min(now.sum3,a.sum1+b.sum2-);

    }

    return(now);

}

int main()

{

    freopen("noip.in","r",stdin);

    freopen("noip.out","w",stdout);

    std::ios::sync_with_stdio(false);

    cin>>n;

    for (int i=;i<=n;i++)

    {

        cin>>a[i];

        b[i-a]=a[i]-a[i-];

    }

    build(,,n-);

    //for (int i=1;i<=2*n;i++){cout<<p[i].h<<" "<<p[i].t<<" "<<p[i].sum<<endl;}

    cin>>m;

    char c;

    for (int i=;i<=m;i++)

    {

        int a1,b1,c1,d1;

        cin>>c;

        if (c=='A')

        {

            cin>>a1>>b1>>c1>>d1;

            change(,a1,b1-,d1);

            if (a1!=) change(,a1-,a1-,c1);

            change(,b1,b1,-(c1+(b1-a1)*d1));

        }

        if (c=='B')

        {

            cin>>a1>>b1; re x;

            if (a1!=b1) x=query(,a1,b1-);

            else x.sum=;

            cout<<x.sum<<endl;

        }

    }

}

巴特西

[JSOI2009]等差数列

最新文章

热门文章