AtCoder Regular Contest 189 (Div. 2)

B - Minimize Sum

给定一个序列 $X$，每次操作可以选择一个 $i$，以 $X_i$ 和 $X_{i+3}$ 为中心，翻转 $X_{i+1}$ 和 $X_{i+2}$。任意次操作后，求最小的 $\sum X_i$。

有一个结论是：对数组进行差分，每次操作等价于交换 $d_i$ 和 $d_{i+2}$。然后就做完了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll x[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i];
    vector<ll> d1,d2;
    for(int i=1;i<n;i++)
        if(i&1) d1.push_back(x[i+1]-x[i]);
        else d2.push_back(x[i+1]-x[i]);
    sort(d1.begin(),d1.end());sort(d2.begin(),d2.end());
    ll ans=x[1],cur=x[1];
    for(int i=1;i<n;i++)
    {
        if(i&1) cur+=d1[i/2];
        else cur+=d2[i/2-1];
        ans+=cur;
    }
    cout<<ans<<'\n';
    return 0;
}

C - Balls and Boxes

有 $n$ 个盒子，第 $i$ 个里有 $a_i$ 个红球，$b_i$ 个蓝球。给定排列 $p,q$，每次操作可以将第 $i$ 个盒子的红球放到第 $p_i$ 个盒子，蓝球放到第 $q_i$ 个盒子。问是否能在若干次操作后使得除了盒子 $x$ 外，其它盒子都为空，求最小操作次数。

套路地，建立两张图，分别是 $i$ 向 $p_i$，$i$ 向 $q_i$ 连边。由于 $p,q$ 是排列，所以得到的一定是若干个环。如果有球的盒子不在 $x$ 所在的环上，那么必然无解。否则，考虑环上离 $x$ 最远的点 $a,b$。那么操作序列一定是

$$\begin{aligned} A&=(a,p[a],p[p[a]],\cdots,x)\\ B&=(b,q[b],q[q[b]],\cdots,x) \end{aligned}$$

只需要求这两个序列的 LCS 就可以了。但这是 $O(n^2)$ 的。可以将 $A$ 中的每个元素映射为 $1,2,\cdots,|A|$，然后对 $B$ 做相同的映射，求映射后的 LIS ，这样就做到了 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N],p[N],q[N];
int fa[N],fb[N];
int find(int x,int *f) {return f[x]==x?x:f[x]=find(f[x], f);}
void merge(int x,int y,int *f)
{
    x=find(x,f),y=find(y,f);
    if(x==y) return;
    f[x]=y;
}
int lis(const vector<int> &v)
{
    vector<int> tail;
    for (int x:v) 
    {
        auto it=lower_bound(tail.begin(),tail.end(),x);
        if(it==tail.end()) tail.push_back(x);
        else *it = x;
    }
    return tail.size();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x;cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>q[i];
    for(int i=1;i<=n;i++) fa[i]=fb[i]=i;
    for(int i=1;i<=n;i++) merge(i,p[i],fa),merge(i,q[i],fb);
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(find(i,fa)!=find(x,fa)&&a[i]==1) flag=false;
        if(find(i,fb)!=find(x,fb)&&b[i]==1) flag=false;
    }
    if(!flag) cout<<-1<<'\n';
    else
    {
        int xa=0,xb=0;
        for(int i=p[x];i!=x;i=p[i])
        {
            if(a[i]==1) 
            {
                xa=i;
                break;
            }
        }
        for(int i=q[x];i!=x;i=q[i])
        {
            if(b[i]==1)
            {
                xb=i;
                break;
            }
        }
        vector<int> va,vb;
        if(xa!=0)
        {
            for(int i=xa;i!=x;i=p[i]) va.push_back(i);
        }
        if(xb!=0)
        {
            for(int i=xb;i!=x;i=q[i]) vb.push_back(i);
        }
        if(xa==0) cout<<vb.size()<<'\n';
        else if(xb==0) cout<<va.size()<<'\n';
        else
        {
            map<int,int> mp;
            int k=(int)va.size();
            for(int i=0;i<k;i++) mp[va[i]]=i+1;
            vector<int> v;
            for(auto i:vb)
                if(mp.find(i)!=mp.end()) v.push_back(mp[i]);
            cout<<va.size()+vb.size()-lis(v)<<'\n';
        }
    }
    return 0;
}

D - Takahashi is Slime

有 $n$ 只史莱姆，每只史莱姆有一个大小。每只史莱姆可以吃掉相邻的大小严格小于它的史莱姆。求每只史莱姆最大的大小是多少。

考虑这样的流程：

1. 先求出当前大小下左侧和右侧第一只不能吃的史莱姆；
2. 吃掉所有当前可以吃的史莱姆，更新大小。

这样的流程最多重复 $O(\log A_{\max})$ 次。因为更新完以后的下一次，如果它吃掉了之前不能吃的史莱姆，它的大小将至少增加到原来的一倍，否则就结束。

第一步和第二步都可以用线段树查询。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node
{
    ll mx;
    ll sum;
}tr[4*N];
int n;
ll a[N];
void build(int l,int r,int p)
{
    if(l==r)
    {
        tr[p].mx=tr[p].sum=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,p*2),build(m+1,r,p*2+1);
    tr[p].mx=max(tr[p*2].mx,tr[p*2+1].mx);
    tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
}
ll qsum(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return tr[p].sum;
    ll ans=0;
    int m=(l+r)>>1;
    if(ql<=m) ans+=qsum(ql,qr,l,m,p*2);
    if(qr>m) ans+=qsum(ql,qr,m+1,r,p*2+1);
    return ans;
}
int qlmx(int x,ll k,int l,int r,int p)
{
    if(l==r) return tr[p].mx>=k?l:-1;
    int m=(l+r)>>1;
    int ans=-1;
    if(x>m)
    {
        if(tr[p*2+1].mx>=k) ans=qlmx(x,k,m+1,r,p*2+1);
        if(ans==-1&&tr[p*2].mx>=k) ans=qlmx(x,k,l,m,p*2);
    }
    else if(tr[p*2].mx>=k) ans=qlmx(x,k,l,m,p*2);
    return ans;
}
int qrmx(int x,ll k,int l,int r,int p)
{
    if(l==r) return tr[p].mx>=k?l:-1;
    int m=(l+r)>>1;
    int ans=-1;
    if(x<=m)
    {
        if(tr[p*2].mx>=k) ans=qrmx(x,k,l,m,p*2);
        if(ans==-1&&tr[p*2+1].mx>=k) ans=qrmx(x,k,m+1,r,p*2+1);
    }
    else if(tr[p*2+1].mx>=k) ans=qrmx(x,k,m+1,r,p*2+1);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[0]=a[n+1]=1e18;
    build(0,n+1,1);
    for(int i=1;i<=n;i++)
    {
        ll ans=a[i];
        for(int l=i,r=i;;)
        {
            int ql=qlmx(l-1,ans,0,n+1,1),qr=qrmx(r+1,ans,0,n+1,1);
            if(ql==l-1&&qr==r+1) break;
            if(ql<l-1) ans+=qsum(ql+1,l-1,0,n+1,1);
            if(qr>r+1) ans+=qsum(r+1,qr-1,0,n+1,1);
            l=ql+1,r=qr-1;
        }
        cout<<ans<<' ';
    }
    return 0;
}