题解:AT_arc187_d [ARC187D] Many Easy Optimizations

_abcd_

2024-11-18 10:20:58

Solution

[ARC187D] Many Easy Optimizations

考虑单次询问怎么做。

不难想到枚举 C 的最大值 mx ,那么对每个 i ,都令 C_i \le mx 的最大值即可。考虑实现:不妨假设 A_i > B_i ,否则只要交换 A_i B_i 即可。令 C_i 一开始为 A_i 。离散化后从大到小枚举每个 mx ,而极差就是 mx - \min C_i ,之后,若存在某个 i 满足 B_i = mx ,就跳出循环;若存在某个 A_i = mx ,就令 C_i = B_i 。最后输出所有极差的最小值即可。

回到原题。同样是枚举 mx ,令 ans_i 表示 m = i 的答案, pre_i 表示 - C_i 的前缀 \max ,则对每个 i ,令 ans_i \gets \min( ans_i, mx + pre_i ) 。考虑用类似历史最值的方法维护 ( ans_i, pre_i )

关于 pre 的维护,每次都会单点修改 C_i ,且 C_i 只会变小,因此需要对 pre 后缀取 \max ,由于其单调递增,因此只要在线段树上二分,然后区间赋值即可。注意,若 mx = B_i ,不能直接退出循环,因为还要对 < i 继续维护。只需要令 C_i - \inf 即可。

至于对 ans_i 的维护,设线段树节点的类型为 ( S, n ) \text{tag} 的类型为 ( a, b, c ) 。若 c 存在,则

( S, n ) + ( a, b, c ) = ( \min( S, n + a, b ), c )

否则

( S, n ) + ( a, b ) = ( \min( S, n + a, b ), n )

那么,有

( S, n ) + ( a, b, c ) + ( a', b', c' ) = ( \min( S, n + a, b, c + a', b' ), c' )

( a, b, c ) + ( a', b', c' ) = ( a, \min( b, b', c + a' ), c' )

对于 c 不存在或 c' 不存在的情况进行类似的讨论,具体可以参考代码。最终复杂度 O( n \log n )

#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define maxn 500005
#define ls pos<<1
#define rs pos<<1|1
#define inf 1000000000
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
void gx(int &x,int y)
{
    if(y>x)
        x=y;
}
void gn(int &x,int y)
{
    if(y<x)
        x=y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
struct Tag
{
    int a,b,c;
    void clr()
    {
        a=inf,b=inf,c=inf;
    }
    void add(Tag t)
    {
        gn(b,t.b);
        if(c<inf)
            gn(b,c+t.a);
        else
            gn(a,t.a);
        if(t.c<inf)
            c=t.c;
    }
}tag[maxn<<2];
int n;
int a[maxn],b[maxn];
int pre[maxn];
int mx[maxn<<2],mn[maxn<<2];
void update(int pos)
{
    mx[pos]=max(mx[ls],mx[rs]);
    mn[pos]=min(mn[ls],mn[rs]);
}
void add(int pos,Tag t)
{
    if(t.c<inf)
        mx[pos]=mn[pos]=t.c;
    tag[pos].add(t);
}
void pushtag(int pos)
{
    add(ls,tag[pos]);
    add(rs,tag[pos]);
    tag[pos].clr();
}
void build_tree(int pos,int l,int r)
{
    tag[pos].clr();
    mx[pos]=pre[r];
    mn[pos]=pre[l];
    if(l==r)
        return;
    int mid=l+r>>1;
    build_tree(ls,l,mid);
    build_tree(rs,mid+1,r);
    update(pos);
}
void cha(int pos,int l,int r,int L,int x)
{
    if(mn[pos]>=x)
        return;
    if(l>=L&&mx[pos]<=x)
    {
        add(pos,{inf,inf,x});
        return;
    }
    pushtag(pos);
    int mid=l+r>>1;
    if(L<=mid)
        cha(ls,l,mid,L,x);
    cha(rs,mid+1,r,L,x);
    update(pos);
}
void print(int pos,int l,int r)
{
    if(l==r)
    {
        printf("%d\n",min(pre[l]+tag[pos].a,tag[pos].b));
        return;
    }
    pushtag(pos);
    int mid=l+r>>1;
    print(ls,l,mid);
    print(rs,mid+1,r);
}
signed main()
{
    n=re();
    for(int i=1;i<=n;i++)
        a[i]=re();
    for(int i=1;i<=n;i++)
        b[i]=re();
    vector<pair<int,int>>tmp;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<b[i])
            swap(a[i],b[i]);
        tmp.push_back({a[i],i});
        tmp.push_back({b[i],i});
    }
    pre[0]=-1e9;
    for(int i=1;i<=n;i++)
        pre[i]=max(pre[i-1],-a[i]);
    build_tree(1,1,n);
    sort(all(tmp));
    reverse(all(tmp));
    for(auto [x,i]:tmp)
    {
        tag[1].add({x,inf,inf});
        if(x>b[i])
            cha(1,1,n,i,-b[i]);
        else
            cha(1,1,n,i,inf-1);
    }
    print(1,1,n);
    return 0;
}