P2672 推销员

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为\(S_i\)米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的\(X\)家住户推销产品，然后再原路走出去。

阿明每走1米就会积累1点疲劳值，向第\(i\)家住户推销产品会积累\(A_i\)点疲劳值。阿明是工作狂，他想知道，对于不同的\(X\)，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入输出格式

输入格式：

第一行有一个正整数\(N\)，表示螺丝街住户的数量。

接下来的一行有\(N\)个正整数，其中第\(i\)个整数\(S_i\)表示第\(i\)家住户到入口的距离。数据保证\(S_1≤S_2≤…≤S_n<10^8\)

接下来的一行有\(N\)个正整数，其中第\(i\)个整数\(A_i\)表示向第\(i\)户住户推销产品会积累的疲劳值。数据保证\(A_i<1000\)

输出格式：

输出\(N\)行，每行一个正整数，第\(i\)行整数表示当\(X=i\)时，阿明最多积累的疲劳值。

【数据说明】

对于 20% 的数据， 1≤N≤20 ；

对于 40% 的数据， 1≤N≤100 ；

对于 60% 的数据， 1≤N≤1000 ；

对于 100% 的数据， 1≤N≤100000 。

---

我就是那种贪心想不全，只会拿暴力数据结构跑的，暴力数据结构还写不出来的那种人。我为什么这么蒻啊。。

稍稍感(胡)性(乱)证明了一下，感觉好像第\(i\)次选的\(i\)个点，第\(i+1\)次全得选上，那好啊我一个个加每次维护一下最大值就好了。

然后开始点线段树\(RMQ\)，开始以为只有单点查询，把区间删减放外面做的，发现不对。。

改，写了个区间查询发现复杂度不对，这个lazy咋打啊....摸了半天，发现和普通的求和线段树的区别是在改变时一是得自下往上改，二是碰见修改区间与节点所带区间相等是得改节点儿子的lazy，而更新这个节点。

---

code:

#include <cstdio>

#define ls id<<1

#define rs id<<1|1

#define mid (L[id]+R[id]>>1)

const int N=100010;

int L[N<<2],R[N<<2],mx[N<<2],pos[N<<2],lazy[N<<2],s[N],a[N];

void build(int id,int l,int r)

{

    L[id]=l,R[id]=r;

    if(l==r) {mx[id]=s[l]+s[l]+a[l];pos[id]=l;return;}

    build(ls,l,mid);

    build(rs,mid+1,r);

    if(mx[ls]<mx[rs])

    {

        mx[id]=mx[rs];

        pos[id]=pos[rs];

    }

    else

    {

        mx[id]=mx[ls];

        pos[id]=pos[ls];

    }

}

void push_down(int id)

{

    mx[id]+=lazy[id];

    if(L[id]!=R[id])

    {

        lazy[ls]+=lazy[id];

        lazy[rs]+=lazy[id];

    }

    lazy[id]=0;

}

void change(int id,int x,int dat)

{

    if(lazy[id]) push_down(id);

    if(L[id]==R[id]) {mx[id]=dat;return;}

    if(x<=mid) change(ls,x,dat);

    else change(rs,x,dat);

    if(mx[ls]<mx[rs])

    {

        mx[id]=mx[rs];

        pos[id]=pos[rs];

    }

    else

    {

        mx[id]=mx[ls];

        pos[id]=pos[ls];

    }

}

void change0(int id,int l,int r,int delta)

{

    if(L[id]==l&&R[id]==r)

    {

        lazy[id]-=delta;

        push_down(id);

        return;

    }

    if(r<=mid) change0(ls,l,r,delta);

    else if(l>mid) change0(rs,l,r,delta);

    else change0(ls,l,mid,delta),change0(rs,mid+1,r,delta);

    if(mx[ls]<mx[rs])

    {

        mx[id]=mx[rs];

        pos[id]=pos[rs];

    }

    else

    {

        mx[id]=mx[ls];

        pos[id]=pos[ls];

    }

}

int main()

{

    int n;

    scanf("%d",&n);

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

        scanf("%d",s+i);

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

        scanf("%d",a+i);

    build(1,1,n);

    int loc=0,las=0;

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

    {

        int lp=pos[1];

        las+=mx[1];

        if(loc<pos[1])

        {

            for(int j=loc+1;j<lp;j++)

                change(1,j,a[j]);

            if(lp<n) change0(1,lp+1,n,s[lp]<<1);

            loc=lp;

        }

        printf("%d\n",las);

        change(1,lp,0);

    }

    return 0;

}

---

2018.6.15