『FLA - I』云音泛

· · 题解

差分、前缀和、队列

你说得对，但是离散化是超纲的。

珍惜身边人。

测试点 1 \sim 6

由于要最大化只有一株玫瑰开放的时刻数量，修改一株玫瑰的种植时间时只可能将其移动到一段没有其他玫瑰开放的时刻。这等价于直接删除这株玫瑰并将只有一株玫瑰开放的时刻数量增加 m。

枚举要删除哪一株玫瑰，然后使用差分和前缀和计算出将其删除后只有一株玫瑰开放的时刻数量。

由于 t_i 与 m 同阶，时间复杂度 O(nm)。

测试点 7 \sim 12

考虑修改第 i 株玫瑰的种植时间对答案产生的影响：答案变为不进行修改时只有一株玫瑰开放的时刻数量，减去不进行修改时有且仅有第 i 株玫瑰开放的时刻数量，加上不进行修改时有且仅有第 i 株玫瑰和另外一株玫瑰共两株玫瑰开放的时刻数量，然后加上 m。

那么只需处理不进行修改时只有一株玫瑰开放的时刻数量，不进行修改时有且仅有第 i 株玫瑰开放的时刻数量和不进行修改时有且仅有第 i 株玫瑰和另外一株玫瑰共两株玫瑰开放的时刻数量这三个信息。它们的计算可以用前缀和与差分轻松完成。

时间复杂度 O(n+m)。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=400'000;
int n,m,ans,l[200'005],r[200'005],sum[400'005],sum1[400'005],sum2[400'005];
inline int w(int l,int r,int *s){return s[r]-s[l-1];}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>l[i],r[i]=l[i]+m-1;
    for(int i=1;i<=n;i++) ++sum[l[i]],--sum[r[i]+1];
    for(int i=1;i<=lim;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=lim;i++) sum1[i]=sum1[i-1]+(sum[i]==1),sum2[i]=sum2[i-1]+(sum[i]==2);
    for(int i=1;i<=n;i++) ans=max(ans,sum1[lim]-w(l[i],r[i],sum1)+w(l[i],r[i],sum2)+m);
    cout<<ans<<'\n';
    return 0;
}

测试点 13 \sim 14

由于 m=1 只需要判断是否存在恰好有两株玫瑰开放的时刻和是否存在三株或更多株玫瑰开放的时刻。这可以用 map 或者别的什么轻松解决。

如果有恰好有两株玫瑰开放的时刻，答案就是不进行任何修改时只有一株玫瑰开放的时刻数量加 2；否则如果有三株或更多株玫瑰开放的时刻，答案就是不进行任何修改时只有一株玫瑰开放的时刻数量加 1；否则答案就是不进行任何修改时只有一株玫瑰开放的时刻数量。

由于 map 在提高组大纲（基础赛允许使用 STL 所以我照样能用，但是我决定严谨一些），这里说明一下如何不超纲地判定。首先对 t 进行排序，如果 t_i \neq t_{i-1} 且 t_i = t_{i+1} 且 t_{i+1} \neq t_{i+2} 则存在恰好有两个玫瑰开放的时刻；如果 t_i \neq t_{i-1} 且 t_i = t_{i+1} =t_{i+2} 则存在有三株或更多株玫瑰开放的时刻。

时间复杂度 O(n \log n)。

测试点 15 \sim 20

由于每一朵玫瑰都只会开放 m 个时刻，所以越早被种下的玫瑰消失越早。先进先出，考虑使用队列维护。具体地，将每一株玫瑰被种下和消失的时间记录在一个序列中，然后对其进行排序、去重，得到一个由全部有玫瑰产生或者消失的时刻组成的序列。

遍历这个序列，维护当前被种下且未消散的玫瑰编号，然后统计有且仅有第 i 株玫瑰开放的时刻数量和有且仅有第 i 株玫瑰和另外 1 株玫瑰共 2 株玫瑰开放的时刻数量。最后枚举删除的玫瑰并计算答案。

注意答案可以达到 3 \times 10^9，会爆 int，获得 95 分很可能是这个原因导致的。

时间复杂度 O(n \log n)，瓶颈在排序。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,pos,t[200'005],p[400'005],w[2][200'005];
long long ans,sum;
queue<int> q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>t[i];
    for(int i=1;i<=n;i++) p[++cnt]=t[i],p[++cnt]=t[i]+m;
    sort(t+1,t+n+1),sort(p+1,p+cnt+1);
    cnt=unique(p+1,p+cnt+1)-p-1;
    for(int i=1;i<=cnt;i++){
        while(!q.empty()&&t[q.front()]+m<=p[i]) q.pop();
        while(pos+1<=n&&t[pos+1]<=p[i]) q.push(++pos);
        if(q.size()==1) w[0][q.front()]+=p[i+1]-p[i],sum+=p[i+1]-p[i];
        if(q.size()==2) w[1][q.front()]+=p[i+1]-p[i],w[1][q.back()]+=p[i+1]-p[i];
    }
    for(int i=1;i<=n;i++) ans=max(ans,sum-w[0][i]+w[1][i]+m);
    cout<<ans<<'\n';
    return 0;
}