P9404 [POI2020-2021R3] Surowa zima 题解

_•́へ•́╬_ · 2023-06-24 20:29:59 · 题解

青蛙。毒瘤。赛时最高 12 分。

吐槽：前两个包数据好水。调试可以试试这些数据：

2 9 2 1
0 9
0 0 0

25

3 22 2 1
1 10 21
0 0 1

69

5 12 1 1
0 5 7 9 11
0 0 1

30

思路

我们首先介绍一下 30 分的做法。

考虑路径大概长啥样。

第一步是从出发点走到第一个充电站。

第二步是走到某一个端点。

第三步是走到另一个端点。

第四步是往回走一点点。也可能不往回走，这一步可能不存在。

详细分析一下：

第一步可能走到左边第一个，也可能走到右边第一个。第二步也有两个方向。所以是有四种情况的。

下文默认是向左走（与样例的方向一致）。下文称第一个充电站为出发点，称相邻两个充电站之间为段。

在出发点左侧的段：

要走过去再走回来，就顺带搞掉了 2k 的长度。这 2k 应当安排在中央。两边的就来回走。

在出发点右侧的段：

直接走过去，不回来，就顺带搞掉了 k 的长度。这 k 就安排在中央。两边来回走，跟上面一样。

往回走一点点时经过的段（这些段一定是所有段的一个后缀，且都在出发点右侧）：

考虑把这些段的贡献记做新贡献减原贡献，就能直接与上面的和相加了。

新贡献计算方法与出发点左侧的段完全一样。

往回走一点点的终点：

终点会在一段的中间。处理一下即可。

• e0 为走到端点并停在端点的代价，适用最右段。
• e1 为走到端点再走回来的代价，适用最左段。
• m0 为走完一段并走到另一端的代价，适用出发点右侧的段。
• m1 为走完一段并回到原端的代价，适用出发点左侧的段。
• m2 为走完一段并停在中间某处的代价，适用第四步的终点段。

code

#include<stdio.h>
#include<algorithm>
#include<vector>
#define N 250009
#define int long long
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,l,k,d,a[N];bool down[N];
inline int e0(int x)
{
    int ans=-x;
    for(int o=(x%k?x%k:k);x>0;x-=k)ans+=o<<1,o+=k;
    return ans;
}
inline int e1(int x)
{
    int ans=0;
    for(int o=(x%k?x%k:k);x>0;x-=k)ans+=o<<1,o+=k;
    return ans;
}
inline int m0(int x)
{
    int ans=x;x-=k;
    for(int o=(x%k?x%k:k),oo=k;x>0;x-=k)
        if(o<oo)ans+=o<<1,o+=k;
        else ans+=oo<<1,oo+=k;
    return ans;
}
inline int m1(int x)
{
    int ans=x<<1;x-=k+k;
    for(int o=(x%k?x%k:k),oo=k;x>0;x-=k)
        if(o<oo)ans+=o<<1,o+=k;
        else ans+=oo<<1,oo+=k;
    return ans;
}
inline int m2(int x)
{
    if(x<=k)return x;
    if(x<=k<<1)return x+x-k;
    int ans=x;x-=k+k;
    for(int o=(x%k?x%k:k),oo=k;x>0?1:(ans+=min(o,oo),0);x-=k)
        if(o<oo)ans+=o<<1,o+=k;
        else ans+=oo<<1,oo+=k;
    return ans;
}
inline int lft(const int&x)
{
    int ans=0;
    for(int i=x,j;;i=j)
    {
        for(j=i-1;j>=0&&down[j];--j);
        if(j>>63){ans+=e1(a[i]);break;}
        ans+=m1(a[i]-a[j]);
    }
    vector<int>b,c;
    for(int i=x,j;;i=j)
    {
        for(j=i+1;j<n&&down[j];++j);
        if(j==n)
        {
            ans+=e0(l-a[i]);
            b.emplace_back(e1(l-a[i])-e0(l-a[i]));c.emplace_back(0);
            break;
        }
        ans+=m0(a[j]-a[i]);
        b.emplace_back(m1(a[j]-a[i])-m0(a[j]-a[i]));
        c.emplace_back(m2(a[j]-a[i])-m0(a[j]-a[i]));
    }
    int bns=0;
    for(int i=b.size()-1,s=0;i>=0;--i)
        bns=min(bns,s+c[i]),s+=b[i];
    return ans+bns;
}
inline int rgt(const int&x)
{
    int ans=0;
    for(int i=x,j;;i=j)
    {
        for(j=i+1;j<n&&down[j];++j);
        if(j==n){ans+=e1(l-a[i]);break;}
        ans+=m1(a[j]-a[i]);
    }
    vector<int>b,c;
    for(int i=x,j;;i=j)
    {
        for(j=i-1;j>=0&&down[j];--j);
        if(j>>63)
        {
            ans+=e0(a[i]);
            b.emplace_back(e1(a[i])-e0(a[i]));c.emplace_back(0);
            break;
        }
        ans+=m0(a[i]-a[j]);
        b.emplace_back(m1(a[i]-a[j])-m0(a[i]-a[j]));
        c.emplace_back(m2(a[i]-a[j])-m0(a[i]-a[j]));
    }
    int bns=0;
    for(int i=b.size()-1,s=0;i>=0;--i)
        bns=min(bns,s+c[i]),s+=b[i];
    return ans+bns;
}
main()
{
    read(n);read(l);read(k);read(d);
    for(int i=0;i<n;read(a[i++]));
    for(int z,u,p;d--;)
    {
        read(z);read(u);read(p);
        for(int x;z--;read(x),down[--x]=0);
        for(int x;u--;read(x),down[--x]=1);
        z=1ll<<60;u=lower_bound(a,a+n,p)-a;
        for(;u<n&&down[u];++u);
        if(u<n)z=min(z,a[u]-p+min(lft(u),rgt(u)));
        for(--u;u>=0&&down[u];--u);
        if(u>=0)z=min(z,p-a[u]+min(lft(u),rgt(u)));
        printf("%lld\n",z);
    }
}

思路

上面那个代码是依托答辩。但是可以吊打（波兰的）国家队。

容易发现 e0、e1、m0、m1、m2 都是可以 \mathcal O(1) 计算的。

容易发现统计到达反方向的端点之前的答案是直接加和的形式，而统计往回走一点点对答案的贡献差是后缀和最小值的形式。

直接上数据结构维护即可。可以使用线段树。时限很够平衡树也行，但是难写一点。封装一下会舒服很多。

code

#include<stdio.h>
#include<set>
#define N 250009
#define ll long long
#define lc ((i)<<1|1)
#define rc ((i)+1<<1)
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,l,k,q,a[N];set<int>qwq;
inline ll e1(int x){return(x%k+x)*(x/k+1ll);}
inline ll e0(int x){return e1(x)-x;}
inline ll m_(int x)
{
    ll l1=x%k?x%k:k,cnt1=(x-1)/k+1+1>>1,l2=k,cnt2=(x-1)/k+1>>1;
    return(l1+l1+(cnt1-1)*k)*cnt1+(l2+l2+(cnt2-1)*k)*cnt2;
}
inline ll m0(int x){return x<=k?x:m_(x-k)+x;}
inline ll m1(int x){return x<=k+k?x+x:m_(x-k-k)+x+x;}
inline ll m2(int x)
{
    if(x<=k)return x;
    if(x<=k<<1)return x+x-k;
    x-=k<<1;ll l1=x%k?x%k:k,cnt1=(x-1)/k+1+1>>1,l2=k,cnt2=(x-1)/k+1>>1;
    return(l1+l1+(cnt1-1)*k)*cnt1+(l2+l2+(cnt2-1)*k)*cnt2+(x+k+k)+
        min(l1+cnt1*k,l2+cnt2*k);
}
inline ll d(int x){return e1(x)-e0(x);}
struct _
{
    ll s0,s1,pfx,pfxmn,sfx,sfxmn;
    inline _ operator+(const _&kkk)const
    {
        return(_){s0+kkk.s0,s1+kkk.s1,pfx+kkk.pfx,min(pfxmn,pfx+kkk.pfxmn)
            ,sfx+kkk.sfx,min(kkk.sfxmn,kkk.sfx+sfxmn)};
    }
}tre[524288];
inline _ g(const int&x)
    {ll u=m0(x),v=m1(x),w=m2(x);return(_){u,v,v-u,w-u,v-u,w-u};}
inline void upd(int i,int l,int r,int p,int x)
{
    if(l==r){tre[i]=g(x);return;}
    int mid=l+r>>1;
    if(p<=mid)upd(lc,l,mid,p,x);
    else upd(rc,mid+1,r,p,x);
    tre[i]=tre[lc]+tre[rc];
}
inline pair<_,_>operator+(const pair<_,_>&x,const _&y)
    {return{x.first,x.second+y};}
inline pair<_,_>operator+(const _&x,const pair<_,_>&y)
    {return{x+y.first,y.second};}
inline pair<_,_>qry(int i,int l,int r,int p)
{
    if(l==r)return{_(),tre[i]};
    int mid=l+r>>1;
    if(p<=mid)return qry(lc,l,mid,p)+tre[rc];
    else return tre[lc]+qry(rc,mid+1,r,p);
}
inline ll qry(const int&x)
{
    if(qwq.size()==1)return min(e1(x)+min(e0(l-x),e1(l-x)),
        e1(l-x)+min(e0(x),e1(x)));
    pair<_,_>tmp=qry(0,0,n-1,lower_bound(a,a+n,x)-a);
    _ lft=tmp.first,rgt=tmp.second;
    return min(e1(*qwq.begin())+e0(l-*--qwq.end())+lft.s1+rgt.s0+
        min(0ll,rgt.sfxmn+d(l-*--qwq.end())),
        e1(l-*--qwq.end())+e0(*qwq.begin())+rgt.s1+lft.s0+
        min(0ll,lft.pfxmn+d(*qwq.begin())));
}
main()
{
    read(n);read(l);read(k);read(q);
    for(int i=0;i<n;read(a[i]),qwq.emplace(a[i++]));
    for(int i=0;i<n-1;++i)upd(0,0,n-1,i,a[i+1]-a[i]);
    for(int z,u,p;q--;)
    {
        read(z);read(u);read(p);
        for(int x,pos;z--;qwq.emplace(x))
        {
            read(x);pos=--x;x=a[x];
            if(x<*qwq.begin()){upd(0,0,n-1,pos,*qwq.begin()-x);continue;}
            if(x>*--qwq.end())
            {
                upd(0,0,n-1,lower_bound(a,a+n,*--qwq.end())-a,
                    x-*--qwq.end());continue;
            }
            set<int>::iterator y=qwq.lower_bound(x),z=y;--y;
            upd(0,0,n-1,lower_bound(a,a+n,*y)-a,x-*y);
            upd(0,0,n-1,pos,*z-x);
        }
        for(int x,pos;u--;qwq.erase(x))
        {
            read(x);pos=--x;x=a[x];
            set<int>::iterator y=qwq.lower_bound(x),z=y;++z;
            upd(0,0,n-1,pos,0);
            if(y==qwq.begin())continue;--y;
            if(z==qwq.end())upd(0,0,n-1,lower_bound(a,a+n,*y)-a,0);
            else upd(0,0,n-1,lower_bound(a,a+n,*y)-a,*z-*y);
        }
        ll ans=1ll<<60;set<int>::iterator it=qwq.lower_bound(p);
        if(it!=qwq.end())ans=min(ans,*it-p+qry(*it));
        if(it!=qwq.begin())--it,ans=min(ans,p-*it+qry(*it));
        printf("%lld\n",ans);
    }
}