推销员 【NOIP 2015】【LG 2672】【BOJ 187 281】 贪心 线段树

Description

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

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

第一行有一个正整数$N$，表示螺丝街住户的数量。
接下来的一行有$N$个正整数，其中第$i$个整数$S_i$表示第$i$家住户到入口的距离.
接下来的一行有$N$个正整数，其中第$i$个整数$A_i$表示向第$i$户住户推销产品会积累的疲劳值。
输出$N$行每行一个正整数，第$i$行整数表示当$X=i$时阿明最多积累的疲劳值。

Simple input

5 
1 2 3 4 5 
1 2 3 4 5

Simple output

15 
19 
22 
24
25

Range

$N \leq 10^5.$

$S_i$单调递增，$S_N \leq 10^8.$

Analyze

令第$i$家住户为$V_i$。令当$X = i$时，使总疲劳度最大的情况下推销的$i$个住户集合为$U_i$，最大疲劳度为$W_i$

可先证明一个结论：$\forall i \in [1,N-1], U_i \subseteq U_{i+1}.$

证明见：《推销员》结论证明

有了这个结论，在已经算完$X=i$时的答案后，可以知道此时选择的$i$个住户都是哪些，下一个点一定在这$i$个住户中最远的一个住户左边或右边。若为左边，将$X=i$时答案加上左边的最大A值即为$X=i+1$时的答案，若在右边，将$X=i$时答案减去当前已选最远住户的S值再加上右边的最大A+2S值即为$X=i+1$时的答案。

因为要进行频繁的区间查询最值，而区间最值满足区间加法、不满足区间减法，同时还要处理已经选择过的住户防止重复被选，因此使用线段树维护区间的A值和A+2S值的最值，将已选择过的住户的A值和A+2S值置为-INF即可防止重复被选。

Source

NOIP 2015

LG 2672

Codevs 5126

BOJ 187 281

Code

#include<bits/stdc++.h>
#define gt() getchar()
#define pt(a) (putchar(a))
#define lch (id<<1)
#define rch (id<<1|1)
const int MAXN = 1E5 + 7;
const long long INF = 1E18 + 7;
struct node_return
{
    int id;
    long long value;
};
struct sgt
{
    int left, right;
    struct node_return one, both;
}tree[MAXN << 2];

int read();
void print(long long x);
void write(long long x);
void build(int id, int l, int r);
struct node_return merge(struct node_return a, struct node_return b);
struct node_return query_both(int id, int l, int r);
struct node_return query_one(int id, int l, int r);
void erase(int id, int p);

int N;
int dis[MAXN];
int w[MAXN];

int main()
{
    N = read();
    for(register int i = 1; i <= N; ++i)
        dis[i] = read();
    for(register int i = 1; i <= N; ++i)
        w[i] = read();
    build(1, 1, N);

    int p;//当前已选的最远住户的编号
    long long ans = 0;
    struct node_return t2, t1 = query_both(1, 1, N);
    p = t1.id;
    ans += t1.value;
    print(ans);
    erase(1, p);
    for(register int i = 2; i <= N; ++i)
    {
        t1.value = -INF;
        t2.value = -INF;
        if(p != 1)
            t1 = query_one(1, 1, p - 1);//查询左侧
        if(p != N)
            t2 = query_both(1, p + 1, N);//查询右侧
        if(t2.value <= -(INF>>1) || t1.value > t2.value - (dis[p]<<1))//左侧更优
        {
            ans += t1.value;
            erase(1, t1.id);//将已经选过的节点的A值置为-INF，防止再次被选
        }
        else//右侧更优
        {
            ans += t2.value - (dis[p]<<1);
            p = t2.id;//更新最远住户编号
            erase(1, t2.id);//将已经选过的节点的A值置为-INF，防止再次被选
               }
        print(ans);
    }
    return 0;
}

void erase(int id, int p)//将p住户的A值置为-INF，防止再次被选
{
    if(tree[id].left == p && tree[id].right == p)
    {
        tree[id].one.value = -INF;
        tree[id].both.value = -INF;
        return;
    }
    if(tree[lch].right >= p)
        erase(lch, p);
    else
        erase(rch, p);
    tree[id].one = merge(tree[lch].one, tree[rch].one);
    tree[id].both = merge(tree[lch].both, tree[rch].both);
    return;
}
struct node_return query_both(int id, int l, int r)//查询[l,r]区间中最大的A+2S值及其位置，使用结构体同时返回值和位置
{
    if(tree[id].left == l && tree[id].right == r)
        return tree[id].both;
    if(tree[lch].right >= r)
        return query_both(lch, l, r);
    else if(tree[rch].left <= l)
        return query_both(rch, l, r);
    else
        return merge(query_both(lch, l, tree[lch].right), query_both(rch, tree[rch].left, r));
}
struct node_return query_one(int id, int l, int r))//查询[l,r]区间中最大的A值及其位置
{
    if(tree[id].left == l && tree[id].right == r)
        return tree[id].one;
    if(tree[lch].right >= r)
        return query_one(lch, l, r);
    else if(tree[rch].left <= l)
        return query_one(rch, l, r);
    else
        return merge(query_one(lch, l, tree[lch].right), query_one(rch, tree[rch].left, r));
}
struct node_return merge(struct node_return a, struct node_return b)
{
    if(a.value > b.value)
        return a;
    return b;
}
void build(int id, int l, int r)
{
    tree[id].left = l;
    tree[id].right = r;
    if(l == r)
    {
        tree[id].one.value = w[l];
        tree[id].one.id = l;
        tree[id].both.value = w[l] + (dis[l]<<1);
        tree[id].both.id = l;
        return;
    }
    build(lch, l, (l+r)>>1);
    build(rch, ((l+r)>>1)+1, r);
    tree[id].one = merge(tree[lch].one, tree[rch].one);
    tree[id].both = merge(tree[lch].both, tree[rch].both);
    return;
}

int read()
{
    int res = 0;
    char ch = gt();
    while(ch < '0' || ch > '9')
        ch = gt();
    while(ch >= '0' && ch <= '9')
    {
        res = (res<<3)+(res<<1)+ch-48;
        ch = gt();
    }
    return res;
}
void print(long long x)
{
    write(x);
    pt('\n');
    return;
}
void write(long long x)
{
    if(x)
    {
        write(x/10);
        pt(x%10 + 48);
    }
    return;
}