题解：AT_agc069_a [AGC069A] Schedule Optimization

· · 题解

好题，我的做法似乎和AT官方完全不同。

首先大致做法比较显然，直接递归处理子问题，处理完 l,mid 和 mid+1,r 然后合并出当前区间的答案，问题在于如何合理的处理出当前区间的答案。

我们先从最简单的例子考虑，现在处理的区间长度为 2，即两个人比赛。两人区间分别为 (l_1,r_1),(l_2,r_2)

不妨分讨

  1. 如果当前的两人区间已经相交了，那么我们是不需要对其进行任何操作的，进一步说，我们需要让胜利的人的时间区间尽可能的长。

    容易发现，我们新产生的区间左端点是固定的，一定为 \max(l_1,l_2)，因为在这个瞬间，两人胜负即可决定，显然向后拖没有意义。

    既然左端点是确定的，那么我们就需要让右端点尽可能的长，我们如果选择 1 号，那么右端点是 r_1，选择 2 号右端点是 r_2，为了让右端点尽可能的长，我们最后的区间实际上是 (\max(l_1,l_2),\max(r_1,r_2))。

  2. 如果当前区间没有相交，即 r_1<l_2。那么为了让二人能拼出胜负，我们需要花钱改动区间，显然当前的最优花费一定是 l_2-r_1，即挪动两者的端点使其相交，再此基础上，我们要让拼出来的区间尽量的长，那么最优策略一定是挪动 l_2 到 r_1，如此操作，拼出来的区间为 (r_1,r_2)。

这样两人的合并就做完了，但是接下来的合并不止于此。

如果我们需要合成四个人的答案， case1 由于没有花费，不会有区别，但是 case2 就有大区别了。

考虑 l_3=3,l_4=3，显然这种情况下合并出来的新的 l'=3，但是当 l' 需要向左移动的时候，我们的花费不再是 1 ，而是 2。

在这种情况下，我们的 case2 也许最优策略不再是移动 l_2 了，因为移动一下 l_2 的花费可能很大，而移动 r_1 的花费一定是 1（建议画个图思考下为什么一定为 1）。我们将移动 l_2 的花费记为 ct(ct\ge1)。

那么此时（即 ct\ne1）我们不妨先贪心最小花费的移动 r_1 至 l_2，然后将 ct-1，返回区间 (l_2,r_2)。考虑这么做为什么是对的，我们当前是移动了 r_1 到了 l_2 的，如果未来我要移动 l_2 到 r_1 这个过程中，我可以撤销这一步的操作，相当于每一步的花费可以减少 1。

这样的想法非常之对，即我当前的 ct= 1 我就一步一步的移动 l_2，如果某时刻 ct\ne 1，我就直接移动 r_1 到此处，然后等待未来可能存在的撤销。

那么如何维护 ct，容易发现，我们只需要维护一个当前人的左端点序列 s 即可，每次处理当前区间，我暴力的把两儿子的 s 合并到当前节点，然后更新，当 l_2 扫到 s 的最大值时，我们让 ct+1，然后删除 s 的最大值。

当我们遇到 ct\ne 1 的操作的时候，我们让 ct-1，然后插入一个 r_1，因为 ct-1 效果的存在区间只持续到 r_1。

代码实现也比较简单，由于数据范围小我就用了 \text{vector} 加暴力排序。实际上复杂度可以做到更优，当前复杂度算是个 n^22^n。但是根本跑不满。

\text{CODE}

#include<bits/stdc++.h>
#define int long long
#define N 600005
#define ls (now<<1)
#define rs (now<<1|1)
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,lim,L[N*4],R[N*4];
int ans,ct[N*4];
struct node
{
    int l,r;
}v[N*4];
vector<int> s[N*4];
node get(int now)
{
    node a=v[ls],b=v[rs];
    for(int x:s[ls])s[now].push_back(x);
    for(int x:s[rs])s[now].push_back(x);
    if(ct[ls])while(ct[ls]--)s[now].push_back(a.l);
    if(ct[rs])while(ct[rs]--)s[now].push_back(b.l);
    sort(s[now].begin(),s[now].end());
    if(a.l>b.l)swap(a,b);
    while(s[now].size()&&b.l==*s[now].rbegin())
    {
        ct[now]++;
        s[now].pop_back();
    }
    if(b.l>a.r)
    {
        if(ct[now]>1)
        {
            ans+=(b.l-a.r);
            s[now].push_back(a.r); 
            ct[now]--;
            return {b.l,b.r};
        }
        if(*s[now].rbegin()<=a.r)
        {
            while(s[now].size()&&*s[now].rbegin()==a.r)ct[now]++,s[now].pop_back();
            ans+=(b.l-a.r);
            return {a.r,b.r};
        }
        else
        {
            int w=*s[now].rbegin();
            while(s[now].size()&&*s[now].rbegin()==w)ct[now]++,s[now].pop_back();
            ct[now]--;
            s[now].push_back(a.r);
            ans+=(b.l-a.r);
            return {w,b.r};
        }
    }
    return {b.l,max(a.r,b.r)};
}
void solve(int now,int l,int r)
{
    if(l==r)
    {
        v[now]={L[l],R[l]};
        ct[now]=1;
        return ;
    }
    int mid=(l+r)>>1;
    solve(ls,l,mid);
    solve(rs,mid+1,r);
    v[now]=get(now);
}
signed main()
{
    n=read();
    lim=(1<<n);
    for(int i=1;i<=lim;i++)L[i]=read(),R[i]=read();
    solve(1,1,lim);
    cout<<ans<<"\n";
    return 0;
}