「BZOJ2388」旅行规划

传送门

分块+凸包

求出前缀和数组s

对于l~r加上k，相当于s[l]~s[r]加上一个首项为k，公差为k的等差数列。r~n加上k*(r-l+1)。

分块之后对每一块维护两个标记，一个记录它加的等差数列（两个等差数列相加仍是等差数列），一个记录它整体加的值。

设首项的标记为A,公差为B

查询一块的最大值，就是询问最大的 s[i] + i*B

可以看成询问平面上的若干横坐标为i,纵坐标为si,斜率为B的直线的最大纵截距，那么维护一个上凸壳即可。

对于散点修改后暴力重构凸包。

对于询问在凸包上三分。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

#define For(i,a,b) for(int i=(a);i<=(b);i++)

#define Rep(i,a,b) for(int i=(a);i>=(b);i--)

const int N=2e5+;

typedef long long LL;

typedef double db;

using namespace std;

int n,m,bl[N],sz,tot,top[];

LL s[N],lz[],A[],B[];

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct pt {

    LL x,y;

    pt(){}

    pt(LL x,LL y):x(x),y(y){}

    friend bool operator <(const pt&A,const pt&B) {

        return A.x<B.x||(A.x==B.x&&A.y<B.y);

    }

}p[N],q[][],D;

pt operator - (const pt&A,const pt&B) { return pt(A.x-B.x,A.y-B.y); }

LL cross(pt A,pt B) { return A.x*B.y-A.y*B.x; }

LL dot(pt A,pt B) { return A.x*B.x+A.y*B.y; }

LL length(pt A) { return dot(A,A); }

void make_ham(int id,int l,int r) {

    For(i,l,r) p[i]=pt(i,s[i]);

    int tp=;

    q[id][++tp]=p[l];

    For(i,l+,r) {

        while(tp>&&cross(q[id][tp]-q[id][tp-],p[i]-q[id][tp-])>=) tp--;

         q[id][++tp]=p[i];

    }

    top[id]=tp;

}

void get_pre() {

    sz=sqrt(n); tot=n/sz; if(n%sz) tot++;

    For(i,,n) {

        bl[i]=(i-)/sz+;

        p[i]=pt(i,s[i]);

    }

    For(i,,tot) {

        int dn=(i-)*sz+,up=min(n,i*sz);

        make_ham(i,dn,up);

    }

}

void down(int x) {

    int l=(x-)*sz+,r=min(n,x*sz);

    if(lz[x]) {

        For(i,l,r) s[i]+=lz[x];

        lz[x]=;

    }

    if(A[x]||B[x]) {

        For(i,l,r) s[i]+=A[x]+B[x]*(i-l);

        A[x]=B[x]=;

    }

}

void change(int l,int r,LL k) {

    down(bl[l]);

    down(bl[r]);

    if(bl[l]==bl[r]) {

        For(i,l,r) s[i]+=k*(i-l+);

        For(i,r+,bl[l]*sz) s[i]+=k*(r-l+);

        make_ham(bl[l],(bl[l]-)*sz+,min(bl[l]*sz,n));

        For(i,bl[l]+,tot) lz[i]+=k*(r-l+);

        return;

    }

    For(i,l,min(n,bl[l]*sz)) s[i]+=k*(i-l+);

    make_ham(bl[l],(bl[l]-)*sz+,min(bl[l]*sz,n));

    For(i,bl[l]+,bl[r]-) {

        A[i]+=k*((i-)*sz+-l+); B[i]+=k;

    }

    For(i,(bl[r]-)*sz+,min(n,bl[r]*sz)) {

        if(i<=r) s[i]+=k*(i-l+);

        else s[i]+=k*(r-l+);

    }

    For(i,bl[r]+,tot) lz[i]+=k*(r-l+);

    make_ham(bl[r],(bl[r]-)*sz+,min(bl[r]*sz,n));

}

LL calc(int x) { return s[x]+lz[bl[x]]+A[bl[x]]+B[bl[x]]*(x-(bl[x]-)*sz-); }

LL get_ans(int x) {

    int l=,r=top[x];

    while(l<=r) {

        if(l+>=r) return max(calc(q[x][l].x),calc(q[x][r].x));

        int mid=((l+r)>>);

        LL a=calc(q[x][mid-].x),b=calc(q[x][mid].x),c=calc(q[x][mid+].x);

        if(a<b&&b<c) l=mid+;

        else if(a>b&&b>c) r=mid-;

        else return b;

    }

    return ;

}

LL qry(int l,int r) {

    LL rs=-1e18;

    if(bl[l]==bl[r]) {

        For(i,l,r) rs=max(rs,calc(i));

        return rs;

    }

    For(i,l,min(n,bl[l]*sz)) rs=max(rs,calc(i));

    For(i,bl[l]+,bl[r]-)

        rs=max(rs,get_ans(i));

    For(i,(bl[r]-)*sz+,r) rs=max(rs,calc(i));

    return rs;

}

#define DEBUG

int main() {

#ifdef DEBUG

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

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

#endif

    read(n);

    For(i,,n) read(s[i]),s[i]+=s[i-];

    get_pre();

    read(m);

    while(m--) {

        int o,l,r; LL v;

        read(o); read(l); read(r);

        if(!o) {

            read(v);

            change(l,r,v);

        }

        else printf("%lld\n",qry(l,r));

    }

    return ;

}

/*

20

32 -5 -28 -1 -39 30 44 38 -44 -6 -8 33 -45 -4 39 -32 -28 -6 42 -24

20

0 7 19 48

0 7 13 5

1 13 17

*/

巴特西

「BZOJ2388」旅行规划

最新文章

热门文章