CF1889C1 Doremy's Drying Plan (Easy Ver.) 题解

FFTotoro · 2023-10-30 20:49:11 · 题解

考虑两个区间会对答案造成什么样的影响。显然重叠部分内的城市能“干涸”当且仅当这个城市仅仅被这两个区间覆盖；不重叠部分的城市能“干涸”当且仅当这个城市仅仅被这一个区间覆盖。

一个城市被几个区间覆盖可以用优先队列贪心来解决；记 c_{l,r} 为 l\sim r 城市中被一个区间覆盖的城市个数。如果两个区间不交，那么答案就是从所有 [l_i,r_i] 中选出最大的两个 c_{l_i,r_i} 相加；如果两个区间相交，答案可以用前面的性质简易统计——只需枚举每个被覆盖两次的城市，然后考虑这两个区间即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m,k,l=0,c=0; cin>>n>>m>>k;
    vector<pii> a(m);
    for(auto &[l,r]:a)cin>>l>>r,l--,r--;
    sort(a.begin(),a.end());
    multiset<pii> q;
    vector<int> w(n),s1(n),s2(n),p;
    vector<pii> b1(n),b2(n);
    for(int i=0;i<n;i++){
      while(!q.empty()&&q.begin()->first<i)q.erase(q.begin());
      while(l<m&&a[l].first<=i)q.emplace(a[l].second,a[l].first),l++;
      if(w[i]=q.size();q.empty())c++;
      if(s1[i]=(i?s1[i-1]:0);q.size()==1)s1[i]++;
      if(s2[i]=(i?s2[i-1]:0);q.size()==2)s2[i]++,
        b1[i]=make_pair(max(q.begin()->second,next(q.begin())->second),q.begin()->first),
        b2[i]=make_pair(min(q.begin()->second,next(q.begin())->second),next(q.begin())->first);
    }
    auto c1=[&](int l,int r){return l<=r?s1[r]-(l?s1[l-1]:0):0;};
    auto c2=[&](int l,int r){return l<=r?s2[r]-(l?s2[l-1]:0):0;};
    for(auto [l,r]:a)p.emplace_back(c1(l,r));
    sort(p.begin(),p.end(),greater<>());
    int s=p[0]+(m>1?p[1]:0);
    for(int i=0;i<n;i++)
      if(w[i]==2)s=max(s,c1(b2[i].first,b1[i].first-1)+c2(b1[i].first,b1[i].second)+c1(b1[i].second+1,b2[i].second));
    cout<<s+c<<'\n';
  }
  return 0;
}