[ZJOI2018]胖

[Luogu4501] [BZOJ5308]

[LOJ2529]有数据就是好

清晰的思路 以及 代码借鉴

对于\(k\)个关键点中的每一个关键点\(a\),二分它能更新到的左端点和右端点

设\(d=|a?p|\)，则\(a\)可以更新\(p\)当且仅当区间\([p?d,p+d]\)中的关键点到\(p\)的距离没有比\(a\)更优的

用\(st\)表维护两个东西 : 区间中到右端点最短的距离 , 区间中到右端点最短的距离

具体细节见代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const LL INF=1e18;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=2e5+5;
const int logN=19;

LL a[MAXN],p[MAXN],len[MAXN],st1[MAXN][logN+1],st2[MAXN][logN+1];
int log2[MAXN];
int n,m,k;
pii pp[MAXN];

inline LL dis(int x,int y){
    if(x>y) return INF;
    return a[y-1]-a[x-1];
}

inline LL calc1(int l,int r){
    if(l>r) return INF;
    int len=log2[r-l+1];
    int pos1=l+(1<<len)-1,pos2=r-(1<<len)+1;
    return min(st1[l][len]+dis(p[pos1],p[r]),st1[pos2][len]);
}
inline LL cal1(int l,int r){//从左边更新过来
    int pos1=lower_bound(p+1,p+k+1,l)-p;// >=
    int pos2=upper_bound(p+1,p+k+1,r)-p-1;// >
    if(pos1>pos2) return INF;
    return calc1(pos1,pos2)+dis(p[pos2],r);
}
inline LL calc2(int l,int r){
    if(l>r) return INF;
    int len=log2[r-l+1];
    int pos=r-(1<<len)+1;
    return min(st2[l][len],st2[pos][len]+dis(p[l],p[pos]));
}
inline LL cal2(int l,int r){
    int pos1=lower_bound(p+1,p+k+1,l)-p;
    int pos2=upper_bound(p+1,p+k+1,r)-p-1;
    if(pos1>pos2) return INF;
    return calc2(pos1,pos2)+dis(l,p[pos1]);
}

inline bool check1(int x,int t){
    if(t<1||t>n) return false;
    int pos=p[x],d=pos-t,l=t-d,r=t+d;
    LL zuo=cal1(l,t),you=cal2(t,r-1);
    LL dist=min(zuo,you),now=dis(t,pos)+len[x];
    if(now<dist) return true;
    else return false;//在[l,r]内比x距离小的,都是比x快的,所以对于x来说不能算贡献
    //实际上对于那些正确的最短路,更新出的答案就是对的,对于那些可以暂时更新的,则体现在[l,r]中没有关键点这样来判断 
}
inline bool check2(int x,int t){
    if(t<1||t>n) return false;
    int pos=p[x],d=t-pos,l=t-d,r=t+d;
    LL zuo=cal1(l+1,t),you1=cal2(t,r-1),you2=cal2(t,r);
    LL dist=min(zuo,you2),now=dis(pos,t)+len[x];
    if(now<dist) return true;
    else if(now==dist){
        LL dist2=min(zuo,you1);
        if(now==dist2) return false;
        else return true;//一定要用到r才更近,那就把贡献算在编号更小的l,总共算这一次贡献, 另一边不会算贡献的
    }
    else return false;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n-1;i++) a[i]=read(),a[i]+=a[i-1];
    for(int i=2;i<=n;i++) log2[i]=log2[i>>1]+1;
    while(m--){
        k=read();
        for(int i=1;i<=k;i++){
            int x=read(),y=read();
            pp[i]=pii(x,y);
        }
        sort(pp+1,pp+k+1);
        for(int i=1;i<=k;i++){
            p[i]=pp[i].first,len[i]=pp[i].second;
            st1[i][0]=len[i],st2[i][0]=len[i];
        }
        for(int j=1;j<=18;j++)
            for(int i=1;i<=k;i++){
                int x=i+(1<<(j-1)),y=i+(1<<j)-1;
                if(y>k) break;
                st1[i][j]=min(st1[i][j-1]+dis(p[x-1],p[y]),st1[x][j-1]);//区间中到右端点最近的
                st2[i][j]=min(st2[i][j-1],st2[x][j-1]+dis(p[i],p[x]));//区间中到左端点最近的
            }
        LL ans=0;
        for(int i=1;i<=k;i++){
            int L=1,R=p[i];
            while(L+1<R){
                int mid=(L+R)>>1;
                if(check1(i,mid)) R=mid;
                else L=mid+1;
            }
            if(check1(i,R-1)) R--;
            int pos1=R;
            L=p[i],R=n;
            while(L+1<R){
                int mid=(L+R)>>1;
                if(check2(i,mid)) L=mid;
                else R=mid-1;
            }
            if(check2(i,L+1)) L++;
            ans+=L-pos1+1;
        }
        printf("%lld\n",ans);
    }
}

[ZJOI2018]胖

原文：https://www.cnblogs.com/lizehon/p/10589464.html