51Nod-1593 公园晨跑

题意

给定一个环，环上有$n$个点，每个点有一个权值$h$代表着如果从$i$到$j$的话，你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。

题解

线段树维护区间最大最小值的坐标和特判相同处理。

首先，面对环和方向性，我们可以把环拆成链式。形成一个$[1,n] \cup [1.n]$的区间对于$X,Y$的查找可以看成两种情况，

• 一种是$X\leq Y$，那么我们寻找的范围就是$[Y+1,X+n-1]$。
• 对于$X>Y$的情况，我们寻找的范围就是$[Y+1,X-1]$。

定义$d[x]$为$x$点到第一个点的距离(线性)。

对于给定的两个点$X,Y$，我们获得的权值是确定的，为$d[Y]-d[X]+2h[X]+2h[Y]$，我们可以将这个算式分为$X$部分和$Y$部分。于是我们就可以将式子转化为

$target = (d[Y]+2h[Y]) - (d[X]-2h[X])$

这个式子求最大值，就是对于每个点求第一部分的最大值和第二部分的最小值。之后由于$X != Y$，所以对于线段树维护的是区间内最大最小值的坐标。当坐标相同时，寻找次一级的最小值或者次一级的最大值。

AC代码(要加入读入优化)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const ll INF = 1e11;
//head
const int maxn = 2e5 + 10;
ll h[maxn],d[maxn],A[maxn],B[maxn];
int mmax[maxn<<2],mmin[maxn<<2];
template <class T>
bool read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-') op = 1;
        else if(c == EOF) return 0;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op) x = -x;
    return 1;
}
inline int Max(int a,int b){
    return A[a] > A[b] ? a : b;
}
inline int Min(int a,int b){
    return B[a] < B[b] ? a : b;
}
inline ll Mmax(ll a,ll b){
    return a>b?a:b;
}
int m,n;
void pushup(int rt){
    mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
    mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        mmax[rt] = l;
        mmin[rt] = l;
        return ;
    }
    int mid = (r+l)>>1;
    build(lson);build(rson);
    pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmax[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Max(res,query_max(L,R,lson));
    if(mid < R) res = Max(res,query_max(L,R,rson));
    return res;
}
int query_min(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmin[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Min(res,query_min(L,R,lson));
    if(mid < R) res = Min(res,query_min(L,R,rson));
    return res;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,2,n+2) read(d[i]),d[n+i] = d[i];
    rep(i,2,n*2+1) d[i] += d[i-1];
    rep(i,1,n+1){
        ll hh;read(hh);
        h[i] = h[i+n] = hh;
    }
    A[0] = -INF;B[0] = INF;
    rep(i,1,n+n+1){
        A[i] = 2*h[i] + d[i];
        B[i] = d[i] - 2*h[i];
    }
    build(1,n*2,1);
    while(m--){
        int l,r;read(l);read(r);
        if(l<=r){
            int st = query_max(r+1,l+n-1,1,2*n,1);
            int ed = query_min(r+1,l+n-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }else{
            int st = query_max(r+1,l-1,1,2*n,1);
            int ed = query_min(r+1,l-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

reference:https://blog.csdn.net/ZLH_HHHH/article/details/74887389