曲调

C++14(g++5.4) 解法, 执行用时: 688ms, 内存消耗: 63080K, 提交时间: 2020-10-01 21:30:08

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct node{
    int l,r,id;
    bool operator<(const node &a)const{
        return r==a.r?l<a.l:r<a.r;
    }
}q[N];
int n,m;
ll mx[N<<2],ans[N],a[N],mi;
vector<ll>V[N<<2];
void build(int l,int r,int rt){
    mx[rt]=INF;
    for(int i=l;i<=r;i++)V[rt].push_back(a[i]);sort(V[rt].begin(),V[rt].end());
    if(l==r)return ;
    int mid=l+r>>1;
    build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int R,int x,int rt){
    if(r<=R){
        auto it=upper_bound(V[rt].begin(),V[rt].end(),a[x]);
        if(it!=V[rt].end())mx[rt]=min(mx[rt],*it-a[x]);
        if(it!=V[rt].begin())mx[rt]=min(mx[rt],a[x]-*(--it));
        if(mx[rt]>=mi)return ;
        if(l==r){mi=min(mi,mx[rt]);return ;}
    }
    int mid=l+r>>1;
    if(R>mid)update(mid+1,r,R,x,rt<<1|1);
    update(l,mid,R,x,rt<<1);
    mx[rt]=min(mx[rt<<1],mx[rt<<1|1]);
    mi=min(mi,mx[rt]);
}
ll query(int l,int r,int L,int R,int rt){
    if(L<=l&&r<=R)return mx[rt];
    int mid=l+r>>1;ll ans=INF;
    if(L<=mid)ans=min(ans,query(l,mid,L,R,rt<<1));
    if(mid<R)ans=min(ans,query(mid+1,r,L,R,rt<<1|1));
    return ans;
}
int main(){
    scanf("%d %d",&n,&m);n++;
    for(int i=2;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
    build(1,n,1);
    for(int i=1;i<=m;i++)scanf("%d %d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+m+1);
    int now=1;
    for(int i=2;i<=n;i++){
        mi=INF;
        update(1,n,i-1,i,1);
        for(;now<=m&&q[now].r+1==i;now++)
            ans[q[now].id]=query(1,n,q[now].l,i-1,1);
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

C++(clang++11) 解法, 执行用时: 818ms, 内存消耗: 41072K, 提交时间: 2021-02-07 21:20:18

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
const int N=3e5+5;
typedef long long ll;
vector<ll>t[400005];
ll a[N],mn,sum[400005],ans[N];
int n,m;
struct node
{
    int l,r,id;
    bool operator<(const node&o)const
    {
        return r<o.r;
    }
}q[N];
void build(int l,int r,int k)
{
    for(int i=l;i<=r;i++) t[k].push_back(a[i]);
    sort(t[k].begin(),t[k].end());
    if(l==r) return;
    int m=l+r>>1;
    build(l,m,k<<1);build(m+1,r,k<<1|1);
}
void Insert(int l,int r,int k,int x,ll v)
{
    if(r<x)
    {
        vector<ll>::iterator it=lower_bound(t[k].begin(),t[k].end(),v);
        if(it!=t[k].end()) sum[k]=min(sum[k],abs(v-(*it)));
        if(it!=t[k].begin()) it--,sum[k]=min(sum[k],abs(v-(*it)));
        if(sum[k]>=mn) return;
    }
    if(l==r) {mn=min(mn,sum[k]);return;}
    int m=l+r>>1;
    if(x>m) Insert(m+1,r,k<<1|1,x,v);
    Insert(l,m,k<<1,x,v);
    sum[k]=min(sum[k],min(sum[k<<1],sum[k<<1|1]));
    mn=min(mn,sum[k]);
}
ll query(int l,int r,int k,int x)
{
    if(r<x) return inf;
    if(l>=x) return sum[k];
    int m=l+r>>1;
    return min(query(l,m,k<<1,x),query(m+1,r,k<<1|1,x));
}
int main()
{
    memset(sum,inf,sizeof(sum));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+1+m);
    build(0,n,1);
    for(int i=0,j=1;i<=n;i++)
    {
        mn=inf;
        Insert(0,n,1,i,a[i]);
        while(j<=m&&q[j].r==i)
            ans[q[j].id]=query(0,n,1,q[j].l-1),j++;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}

详情