专栏文章

题解：AT_arc187_d [ARC187D] Many Easy Optimizations

__abcd_
AT_arc187_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir3tyxv
此快照首次捕获于
2025/12/04 15:18
3 个月前
此快照最后确认于
2025/12/04 15:18
3 个月前
查看原文

[ARC187D] Many Easy Optimizations

考虑单次询问怎么做。
不难想到枚举 CC 的最大值 mxmx，那么对每个 ii，都令 CiC_i 取 ≤mx\le mx 的最大值即可。考虑实现：不妨假设 Ai>BiA_i > B_i，否则只要交换 AiA_i 和 BiB_i 即可。令 CiC_i 一开始为 AiA_i。离散化后从大到小枚举每个 mxmx，而极差就是 mx−min⁡Cimx - \min C_i，之后，若存在某个 ii 满足 Bi=mxB_i = mx，就跳出循环；若存在某个 Ai=mxA_i = mx，就令 Ci=BiC_i = B_i。最后输出所有极差的最小值即可。
回到原题。同样是枚举 mxmx，令 ansians_i 表示 m=im = i 的答案，preipre_i 表示 −Ci- C_i 的前缀 max⁡\max，则对每个 ii，令 ansi←min⁡(ansi,mx+prei)ans_i \gets \min( ans_i, mx + pre_i )。考虑用类似历史最值的方法维护 (ansi,prei)( ans_i, pre_i )。
关于 prepre 的维护，每次都会单点修改 CiC_i，且 CiC_i 只会变小，因此需要对 prepre 后缀取 max⁡\max，由于其单调递增，因此只要在线段树上二分，然后区间赋值即可。注意，若 mx=Bimx = B_i，不能直接退出循环，因为还要对 <i< i 继续维护。只需要令 CiC_i 为 −inf⁡- \inf 即可。
至于对 ansians_i 的维护，设线段树节点的类型为 (S,n)( S, n )，tag\text{tag} 的类型为 (a,b,c)( a, b, c )。若 cc 存在，则 (S,n)+(a,b,c)=(min⁡(S,n+a,b),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 ) = ( \min( S, n + a, b ), n )
那么，有 (S,n)+(a,b,c)+(a′,b′,c′)=(min⁡(S,n+a,b,c+a′,b′),c′)( 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′)( a, b, c ) + ( a', b', c' ) = ( a, \min( b, b', c + a' ), c' )
对于 cc 不存在或 c′c' 不存在的情况进行类似的讨论，具体可以参考代码。最终复杂度 O(nlog⁡n)O( n \log n )。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...