hdu6800

航电多校第三场

　　这道题的思维很是巧妙啊，虽然赛时大概有了想法，但是当初没学会树套树，还是过不了的啊，感觉题解有点太难懂了，再一篇博客，分享一下自己标注过的std；

　　首先是这题一共只有两只手，而且按顺序跑n个点，也就是说，假如dp[i][j]代表着你左手在i，右手在j的时候的最优解，其实dp[i][j]=dp[j][i];所以说当最大的点为i时，你只需要关心另外一只手放在哪个点了就行了，也就是说dp[i+1][j]只和dp[i][*]有关系，和dp[i-1][*]只有间接关系。

　　然后为了dp好弄一点，dp存的值不是当前答案时多少，而是我们通过交换手省下了多少的步长。

　　首先除了dp[i][i-1]以外，dp[i][j]都是等于dp[i-1][j]的，为什么呢，因为从dp[i-1][j]到dp[i][j]，我们不会换手，所以说我们不会省下任何步长，所以我们每跑一个点，只需要更新dp[i][i-1]即可。

　　然后dp[i][i-1]怎么更新呢，就变成了二维平面上，找一个j点与这个点的曼哈顿距离加上dp[i][j]最小，这个可以通过树套树loglog时间解决

#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int maxn = (int)1e5 + 1;

namespace Memory {
    const int maxm = maxn * 18 + 1, maxl = maxm * 8 + 1;
    int pool[maxm], *pool_tail;
    LL info[maxl], *info_tail;

    inline void reset() {
        pool_tail = pool;
        info_tail = info;
    }
    inline int *ask32(int len) {
        int *ret = pool_tail;
        pool_tail += len;
        return ret;
    }
    inline LL *ask64(int len) {
        LL *ret = info_tail;
        info_tail += len;
        return ret;
    }
}

int n, qtot;
LL dp[maxn];
pair<int, int> seq[maxn], que[maxn];

inline void upd_min(LL &x, LL y) {
    x > y && (x = y);
}

inline bool cmp_y(int const &u, int const &v) {
    return que[u].second < que[v].second;
}

struct Segment {
    int ytot, *yque;
    LL *info;
} seg[maxn << 1 | 1];

inline int seg_idx(int L, int R) {//线段树L-R的hash映射
    return (L + R) | (L < R);
}


void seg_init_inner(Segment &rt, int L, int R) {
    if(L == R)
        return;
    int M = (L + R) >> 1;
    seg_init_inner(rt, L, M);
    seg_init_inner(rt, M + 1, R);
    LL *cur = rt.info + (seg_idx(L, R) << 2);
    LL *lft = rt.info + (seg_idx(L, M) << 2);
    LL *rht = rt.info + (seg_idx(M + 1, R) << 2);
    cur[0] = min(lft[0], rht[0]);
    cur[1] = min(lft[1], rht[1]);
    cur[2] = min(lft[2], rht[2]);
    cur[3] = min(lft[3], rht[3]);
}

void seg_init_outer(int L, int R) {
    
    static int ord[maxn];
    
    if(L < R) {
        int M = (L + R) >> 1;
        seg_init_outer(L, M);
        seg_init_outer(M + 1, R);
        inplace_merge(ord + L, ord + M + 1, ord + R + 1, cmp_y);//按que[u].second 有序合并
    }
    else
    {
        ord[L] = L;
    }
    
    Segment &rt = seg[seg_idx(L, R)];
    
    rt.ytot = 1;
    for(int i = L + 1; i <= R; ++i)
        rt.ytot += cmp_y(ord[i - 1], ord[i]);//L到R中到底有多少个不同的y值
    
    rt.yque = Memory::ask32(rt.ytot);
    rt.info = Memory::ask64(((rt.ytot - 1) << 1 | 1) << 2); ((n-1)*2+1)*4;
    
    
    for(int i = L, j = 0; i <= R; ++j) {
        int u = ord[i++], y = que[u].second, xL = que[u].first, xR = xL;
        
        
        for(int v; i <= R && !cmp_y(u, v = ord[i]); ++i) { //如果u+1和u同高，继续u++
            int tmp = que[v].first;
            if(tmp < xL) {
                xL = tmp;
            } else if(tmp > xR) {
                xR = tmp;
            }
            //扩充当前的左右边界
        }
        //这里的j是按高度不同才增一次的
        rt.yque[j] = y;
        
        LL *val = rt.info + (seg_idx(j, j) << 2);//4*j
        val[0] = -xR - y;//各个象限对应的值
        val[1] = -xR + y;
        val[2] = xL - y;
        val[3] = xL + y;
    }
    //内层的线段树
    //内层的线段树
    seg_init_inner(rt, 0, rt.ytot - 1);
}

inline void seg_update_inner(Segment &rt, int y, LL val[]) {
    
    for(int L = 0, R = rt.ytot - 1; L <= R; ) {
        LL *cur = rt.info + (seg_idx(L, R) << 2);
        upd_min(cur[0], val[0]);
        upd_min(cur[1], val[1]);
        upd_min(cur[2], val[2]);
        upd_min(cur[3], val[3]);
        if(L == R)
            break;
        
        int M = (L + R) >> 1;
        
        if(y <= rt.yque[M]) {
            R = M;
        } else {
            L = M + 1;
        }
        
        
    }
    
}

inline void seg_update_outer(int pos) {
    int x = que[pos].first, y = que[pos].second;
    LL v = dp[pos], val[5] = {
        v - x - y,
        v - x + y,
        v + x - y,
        v + x + y
    };
    for(int L = 0, R = qtot - 1; L <= R; ) {
        
        seg_update_inner(seg[seg_idx(L, R)], y, val);
        
        if(L == R)
            break;
        
        int M = (L + R) >> 1;
        
        if(pos <= M) {
            
            R = M;
            
        } else {
            L = M + 1;
        }
    }
}

inline LL seg_query_left_inner(Segment &rt, int x, int y) {
    LL ret = LLONG_MAX;
    for(int L = 0, R = rt.ytot - 1; L <= R; ) {
        LL *cur = rt.info + (seg_idx(L, R) << 2);
        if(y <= rt.yque[L]) {
            upd_min(ret, cur[1] - y);
            break;
        } else if(y >= rt.yque[R]) {
            upd_min(ret, cur[0] + y);
            break;
        }
        
        int M = (L + R) >> 1;
        if(y <= rt.yque[M]) {
            LL *rht = rt.info + (seg_idx(M + 1, R) << 2);
            upd_min(ret, rht[1] - y);
            R = M;
        } else {
            LL *lft = rt.info + (seg_idx(L, M) << 2);
            upd_min(ret, lft[0] + y);
            L = M + 1;
        }
        
    }
    if(ret != LLONG_MAX)
        ret += x;
    return ret;
}

inline LL seg_query_right_inner(Segment &rt, int x, int y) {
    LL ret = LLONG_MAX;
    for(int L = 0, R = rt.ytot - 1; L <= R; ) {
        LL *cur = rt.info + (seg_idx(L, R) << 2);
        if(y <= rt.yque[L]) {
            upd_min(ret, cur[3] - y);
            break;
        } else if(y >= rt.yque[R]) {
            upd_min(ret, cur[2] + y);
            break;
        }//已经可以确定在哪个象限有答案了
        
        int M = (L + R) >> 1;
        
        if(y <= rt.yque[M]) {
            
            LL *rht = rt.info + (seg_idx(M + 1, R) << 2);
            //在右上方的点的贡献也可以算了
            upd_min(ret, rht[3] - y);
            R = M;//从新区间L-M再来
        } else {
            LL *lft = rt.info + (seg_idx(L, M) << 2);
            upd_min(ret, lft[2] + y);
            L = M + 1;
        }
    }
    if(ret != LLONG_MAX)
        ret -= x;
    return ret;
}

inline LL seg_query_outer(int pos) {
    int x = que[pos].first, y = que[pos].second;
    LL ret = dp[pos];
    for(int L = 0, R = qtot - 1; L < R; ) {
        int M = (L + R) >> 1;
        
        if(pos <= M) {
            upd_min(ret, seg_query_right_inner(seg[seg_idx(M + 1, R)], x, y));
            R = M;
        } else {
            upd_min(ret, seg_query_left_inner(seg[seg_idx(L, M)], x, y));
            L = M + 1;
        }
        
    }
    
    return ret;
}

void solve() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &seq[i].first, &seq[i].second);
        que[i] = seq[i];
        dp[i] = 0;
    }
    sort(que, que + n);
    qtot = unique(que, que + n) - que;

    Memory::reset();
    seg_init_outer(0, qtot - 1);//线段树初始化
    

    LL ans = 0, sum = 0;
        
    int las = lower_bound(que, que + qtot, seq[0]) - que;
    
    for(int i = 1; i < n; ++i) {
        LL adt = abs(seq[i].first - seq[i - 1].first) + abs(seq[i].second - seq[i - 1].second);
        int pos = lower_bound(que, que + qtot, seq[i]) - que;
        LL best = seg_query_outer(pos) - adt;//以换手的代价跑到pos，省了多少的代价
        
        if(dp[las] > best) {//比已经省下的多
            
            ans=min(ans , dp[las] = best );
            
            seg_update_outer(las);
        }
        
        sum += adt;
        las = pos;
    }
    printf("%lld
", ans + sum);
}
int main() {
    int T;
    scanf("%d", &T);
    for(int Case = 1; Case <= T; ++Case) {
        // printf("Case #%d:
", Case);
        solve();
    }
    return 0;
}