题目描述

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

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

题解:

这道题是可以很简单的贪心解决的，但是我最近开始刷数据结构的题，所以这道题用线段树来解决
参考题解
当i==n的时候好做，答案就是最长的距离2+所有点的疲劳值
当i！=n时，我们完全可以从上一个状态删去一点推到出来，也就是倒着做这个题
大题思路：
1.当i==n时好说，每一次的选择都是基于上一次的
2.当我们求每一个状态时，只需要关注当前的A值的和，以及所选点中最短的点的距离len，因为len是所要走的路径
关键在于每次都是删除一个点，怎么删去正确的点呢？
我们用l和r分别表示当前所选的最小的点的坐标，以及最大点的坐标
删点有两种情况：
1.如果删去的点时最后一个点，最远距离就发生改变了，原本最远距离是最后一个点，现在最远距离成为最后一个点的上一个点，（上一个点的意思是在所选的点中，最后一个点的上一个点，而不一定是最后一个点紧靠着左边的点），此时更新最远距离，删去原先的距离2，加上现在的最远距离*2，同时答案删去A[r]，即删去最后一个点
2.当删去的点不是最后一个点时，最远距离没变，只需要删去A[i]即可，A[i]为区间内的最小点
两个答案我们要取最大值，也就是最疲劳
在情况2中，我们要删去中间的值，区间长度未变，所以我们用线段树来维护区间内的最小疲劳值点以及相应的坐标
删除点就是将该点的值改为INF，这样就永远取不到，这个操作用线段树的单点修改实现
在操作1中，如果求的最后一个点的前一个点，这个好说用一个链表就可以
代码有详细注释
代码为题解里的代码，因为我的代码莫名wa了，没调出来

代码：

#include<bits/stdc++.h>
using namespace std;

//这里用pair来存区间min值和min值下标

const int MAXN = 1e5 + 10;
const int INF = 1e9;

struct house {
    int a,s;
    bool operator < (const house &b) const {return a < b.a;}
} node[MAXN];

int n,pre[MAXN],nxt[MAXN];//pre、nxt：链表
int tree[MAXN << 2],pos[MAXN << 2];//tree：线段树区间min，pos：线段树区间min下标
int ans[MAXN],l,r;//ans：x为不同数值时的答案数组

#define l ll//懒得换变量名了，就define一下
#define r rr//到时候会undef

void pushup(int root) {//更新
    if(tree[root << 1 | 1] < tree[root << 1]) {//如果右子树更优
        tree[root] = tree[root << 1 | 1];//只能存右子树的答案了
        pos[root] = pos[root << 1 | 1];
    } else {
        tree[root] = tree[root << 1];//否则存左子树，这样可以让下标尽量小
        pos[root] = pos[root << 1];
    }
}

void build(int root,int l,int r) {//简单的建树
    if(l == r) {
        tree[root] = node[l].a;
        pos[root] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    pushup(root);
}

void update(int root,int l,int r,int pos,int val) {//简单的更新
    if(l == r && l == pos) {
        tree[root] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(root << 1,l,mid,pos,val);
    else update(root << 1 | 1,mid + 1,r,pos,val);
    pushup(root);
}

pair<int,int> getmin(pair<int,int> &a,pair<int,int> b) {//类似于min函数，用来找两个pair<int,int>中最小值较小的那个（即当前的返回值）
    if(b.first < a.first) swap(a,b);
}

pair<int,int> query(int root,int l,int r,int L,int R) {
    if(L <= l && r <= R) return make_pair(tree[root],pos[root]);
    int mid = (l + r) >> 1;
    pair<int,int> res = make_pair(INF,INF);
    if(L <= mid) getmin(res,query(root << 1,l,mid,L,R));//这里用到了getmin，可以自己研究一下
    if(R > mid) getmin(res,query(root << 1 | 1,mid + 1,r,L,R));
    return res;
}

#undef l
#undef r//说了会undef

void Delete(int pos) {
    pre[nxt[pos]] = pre[pos];
    nxt[pre[pos]] = nxt[pos];
}//删除节点函数。。。

int main () {
    ios::sync_with_stdio(0);//优化
    cin >> n;
    for(register int i = 1;i <= n; ++i)
        cin >> node[i].s;
    for(register int i = 1;i <= n; ++i) {
        cin >> node[i].a;
        pre[i] = i - 1;
        nxt[i] = i + 1;//链表初始化
        ans[n] += node[i].a;//最终答案
    }
    build(1,1,n);//建树
    l = 1,r = n;//左右端点（实际只有 r 有用）
    ans[n] += node[r].s * 2;//答案要加上dis
    for(register int i = n - 1;i >= 1; --i) {//倒推答案
        pair<int,int> tmp = query(1,1,n,l,r - 1);//方案1 中用线段树
        int ans1 = ans[i + 1] - tmp.first;//方案1
        int ans2 = ans[i + 1] - node[r].a - node[r].s * 2 + node[pre[r]].s * 2;//方案2，也就是减去 r 的s*2和a，再加上新r的s*2
        if(ans1 < ans2) {//如果方案2更疲劳 
            int ss = r;
            r = pre[r]; Delete(ss);//删除右端点，更新右端点
            ans[i] = ans2;//更新答案
        } else {
            Delete(tmp.second);//删除当前下标
            update(1,1,n,tmp.second,INF);//更新，把当前A变成INF
            ans[i] = ans1; //更新答案
        }
    }
    for(register int i = 1;i <= n; ++i)
        cout << ans[i] << endl;//输出
    return 0;//华丽丽地结束
}