CEOI2021 Tortoise

题意

个位置，每个位置可能有游乐园或若干糖果。

Tom 在 时刻位于位置 ，每 时刻可以移动 位置。有糖果可以带一个糖果，然后（必须）去到一个游乐园放下糖果（带上与放下均不消耗时间）。当时间严格大于 时位置 上的糖果会消失。

问最少消失几颗糖果。

思路

初步分析

显然我们带一个糖果之后，必须去左右最近的一个游乐园放下去，所以我们定义两个游乐园及中间的部分为一个区块（一个游乐园允许在多个区块中），特殊的，如果最左边没有游乐园我们依然视其为一个区块（注意最右边不算）。我们假定每个区块中至少有一颗糖果，否则我们忽略这个区块。对于总的移动情况，我们肯定是从左到右依次处理每个区块。

然后考在区块内的移动方式，分为三种：

  1. 左循环：

    1
    2
    3
    graph LR
        游乐园-.出程.->糖果
        糖果-.归程.->游乐园

  2. 右循环：

    1
    2
    3
    graph LR
        糖果-.归程.->游乐园
        游乐园-.出程.->糖果

  3. 漫游（从官方题解生草出来的）：

    1
    2
    3
    graph LR
        1[游乐园]-.出程.->糖果
        糖果-.归程.->2[游乐园]

那么对于一个区块内，我们显然是先从左到右做若干个左循环，然后做一次漫游，然后从左到右做若干个右循环。

如果我们规定 A 必须从最左边走到最右边的话，显然漫游是不会增加我们总的移动时间的，所以我们规定每个区块都必须进行一次有糖果的漫游。

对于任意一个不进行漫游的糖果，我们显然是选择最短的一个循环把它做掉。

因为总的能移动的时间是有限的，所以我们考虑先处理距离最短的糖果。

于是我们对这个距离排序，然后一颗一颗插入糖果（循环），只要合法就继续。

这边建议您可以先到此为止，尝试写一个 的做法。

关于正确性，你考虑如果一个糖果 试图弹出前面的糖果 以使得自己合法，那么有两种情况：

  1. 的位置大于 ，这样显然不优；
  2. 的位置小于 ，这样看起来似乎我们可以给中间的糖果多一些机会，然而因为如果这中间有任何没有被插入的糖果，那么其耗时一定是大于被弹出的糖果的（否则在 加入之前就被加入了），故插入任何糖果都会使得 不合法。

于是这样并不会带来更多的收益，所以我们无需考虑它的发生。

做法一

二步分析

对于满分，我们可以用一些数据结构维护。

以上官方题解原话。

我们发现这题解太棒了，以后 Ynoi 的题目都可以这么写题解：

这道题要维护……我们可以用一些数据结构维护。

首先我们分析一下加入一颗糖会对它之后产生什么影响，由于我们插入的是循环，所以我们可以把贡献打到其对应的游乐园上。

那么我们的需求就分为两个部分，挂在游乐园上的循环对时间的要求以及游乐园之间的漫游对时间的要求。糖果的具体可行性要根据左右循环以及漫游进行讨论：

  1. 左循环：

    因为所有距离比这颗糖果小的糖果都已经计算过了，所以这颗糖果一定是最右的一个。我们对游乐园 维护一个 表示我们在 时刻在游乐园 ，并且接下来准备润到右边的区块（左边的区块被放弃），这样我们就可以判断这颗糖果是否可行。

    我们再维护一个 表示我们第一次到达游乐园 是在时刻 ，我们可以维护出 表示游乐园 最晚能在什么时候到达，这样就可以判断后面的循环是否合法。

  2. 右循环：

    同理，这颗糖果是最左的一个，那么我们相当于在原有的 上加了一个循环，为了维护 的含义，我们直接在 上减去这个距离。

  3. 漫游：

    我们可以先对每一个区块钦定最右的糖果，表示这颗糖果将会漫游。

    在加循环时，若我们将令这个糖果进行循环，就将这个钦定向左转移。

    这样就会变成这个区间左边的游乐园的 最大值受到了一定的限制，即 。

    注意最左若没有游乐园则需要特殊处理。

我们可以令 始终减去 ，对 同样操作，这样就可以将判断是否大于某个值变为是否大于零，便于数据结构维护。

我们发现 均需要支持单点查询，后缀加减。 还需要额外支持单点修改，后缀最小值。线段树即可。

实现

处理最左边的时候，可以设 有一个游乐园，但是所有点与它的距离为 。

无论是左循环还是右循环，都要注意可能对 做出限制。

不然完整数据会挂一个点（不清楚谷上有没有这个点）。

CODE

看了看代码感觉 与 可以去掉其中一个，但是我不想动脑了，于是喜提最劣解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500010,FSIZE=1<<24,INF=0x33ffffff;
using ll=long long;
int n,a[N],l[N],lf[N],r[N],s[N];
ll ans;
struct candy{int d,x,t,p;};
vector<candy> v;
vector<int> c[N];
struct node0{
    int a;
    void operator+=(int x){a+=x;}
    void pushup(node0,node0){}
};
struct node1{
    int a,mi;
    node1(){mi=INF;}
    node1(int x){a=mi=x;}
    void operator+=(int x){a+=x;mi+=x;}
    void pushup(node1 &x,node1 &y){mi=min(x.mi,y.mi)+a;}
};
template<typename node>struct ST{
    node a[N<<2];
    void pushdown(int x){
        if(a[x].a){
            a[x<<1]+=a[x].a;
            a[x<<1|1]+=a[x].a;
            a[x].a=0;
        }
    }
    void pushup(int x){
        for(;x;x>>=1) a[x].pushup(a[x<<1],a[x<<1|1]);
    }
    template<class T>int trans(int x,T work){
        int m=1,l=0,r=n,mid;
        for(;l<r;){
            pushdown(m);
            if((mid=(l+r)>>1)<x){
                l=mid+1;
                m=m<<1|1;
            }else{
                work(m<<1|1);
                r=mid;
                m<<=1;
            }
        }
        return(m);
    }
    void plus(int x,int t){
        if(x>n) return;
        int m=trans(x,[&](int x){a[x]+=t;});
        a[m]+=t;
        pushup(m>>1);
    }
    int& operator[](int x){
        return(a[trans(x,[](int){})].a);
    }
    void tag(int x,int t){
        int m=trans(x,[](int){});
        a[m]=t;
        pushup(m>>1);
    }
    int query(int x){
        int re=INF;
        return(min(re,a[trans(x,[&](int x){re=min(re,a[x].mi);})].a));
    }
};
ST<node0> in,out;
ST<node1> mx0,mx1;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    bool f=1;
    for(;48>*InF||*InF>57;f^=*InF++=='-');
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    x=f?x:-x;
}
bool solve(candy x){
    int g=lf[x.x],bk=c[g].back();
    return((x.x-1)<<1>=(x.t?in:out)[x.p]+(x.d>>1)&&mx0.query(x.p+!x.t)>=x.d&&
        (a[x.x]>1||out[g]<=((bk-1)<<1)-g+bk)&&mx1.query(x.p)>=x.d);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    l[0]=-INF;
    for(int i=1;i<=n;++i){
        read(a[i]);
        if(~a[i]) ans+=a[i];
        lf[i]=max(l[i]=~a[i]?l[i-1]:i,0);
        if(a[i]>0){
            s[lf[i]]+=a[i];
            c[lf[i]].push_back(i);
        }
        out[i]=in[i]=i-1;
        mx0[i]=INF;
    }
    r[n+1]=INF;
    for(int i=n;i;--i) r[i]=~a[i]?r[i+1]:i;
    for(int i=1;i<=n;++i){
        sort(c[i].begin(),c[i].end());
        mx1.tag(i,~a[i]||r[i+1]==INF||c[i].empty()?INF:((c[i].back()-1)<<1)+i-c[i].back()-out[i]);
        if(a[i]>0)
            v.push_back({min(i-l[i],r[i]-i)<<1,i,i-l[i]>r[i]-i,(i-l[i]>r[i]-i?r:l)[i]});
    }
    sort(v.begin(),v.end(),[](candy a,candy b){return(a.d<b.d);});
    for(auto i:v)
        for(int g;a[i.x];--s[g],--ans)
            if((s[g=lf[i.x]]>1||r[i.x]==INF)&&solve(i)){
                auto &bk=c[g];
                if(!--a[i.x]&&bk.back()==i.x&&r[i.x]<INF){
                    bk.pop_back();
                    mx1.tag(g,((bk.back()-1)<<1)+g-bk.back()-out[g]);
                }
                int p=min(INF,mx0[i.p]),s=((i.x-1)<<1)-(i.d>>1);
                mx0.tag(i.p,i.t?min(s-in[i.p],p-i.d):min(s-out[i.p],p));
                in.plus(i.p+1,i.d);
                mx0.plus(i.p+1,-i.d);
                out.plus(i.p,i.d);
                mx1.plus(i.p,-i.d);
            }else break;
    for(int i=1;i<=n;++i) ans-=i==r[i]&&s[lf[i-1]]>0;
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return(0);
}

做法二

我们发现可以按照区块顺序从前往后扫，然后对块内按照上述处理糖果。

这样就无需处理跨块的时间贡献了，使用可撤销贪心维护一个堆就没了。

代码没写，感觉很好写。

≡