[COTS/CETS 2018] 直方图 Histogram 题解

· · 题解

从部分分 h_i\le 1000 出发，枚举合法矩形的高度 h：从上往下做扫描线，考虑维护所有高度 \ge h 的矩形构成的横向“连续段”，就可以对于 w=1,2,\ldots,n 计算出底边长为 w、高度为 h 的矩形的个数 c_w（对于一个长度为 k 的连续段，底边长为 w(1\le w\le k) 的矩形有 k-w+1 个）。

对于每个高度 h，可以求出矩形底边边长的最小值 w_{\min} 使得 h\cdot w_{\min}\ge p，答案即为 r_h=\sum\limits_{w=w_{\min}}^n c_w。

接下来考虑 h_i 比较大的时候怎么做。考虑扫描线时，从 h'+1 扫描到 h' 时，r_{h'}\ne r_{h'+1} 只可能有两种情况：（1）两者对应的 w_{\min} 不相等；（2）两者对应的连续段形态不相等，此时必然存在 h_i=h'，这样连续段形态才会发生变化。前者仅有不超过 n 种情况，因为 w_{\min} 只有 n 种；后者也不超过 n 种情况，因为 h_i 也最多只有 n 种。于是只有最多 2n 个分界点，这些分界点之间所有 h' 对应的 r_{h'} 都是相等的。

于是考虑开一个线段树，对于每个 w=1,2,\ldots,n，在扫描的过程中实时维护底边长为 w 的矩形的答案。我们要做的事情有如下两种：

上面两个操作可以使用树状数组维护：具体维护方法可以参照该教程；而连续段形态可以使用 std::set 维护。时间复杂度 O(n\log n)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
namespace IAOI_lib{
  template<typename T> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(){}
      void resize(int n){
        t.resize(n);
      }
      fenwick_tree(int n){
        resize(n);
      }
      inline int lowbit(int x){
        return x&-x;
      }
      inline void add(int p,T d){
        if(p<0||p>=t.size())return;
        t[p++]+=d;
        while((p+=lowbit(p))<=t.size())t[p-1]+=d;
      }
      inline T sum(int p){
        if(p<0||p>=t.size())return 0;
        T s=t[p++];
        while((p-=lowbit(p))>0)s+=t[p-1];
        return s;
      }
  };
}
template<typename T> class arithmetic_fenwick_tree{
  private:
    IAOI_lib::fenwick_tree<T> c,c1,c2;
    inline void add(int p,T x){
      c.add(p,x),c1.add(p,x*p),c2.add(p,x*p*p);
    }
  public:
    arithmetic_fenwick_tree(int n){
      c.resize(n),c1.resize(n),c2.resize(n);
    }
    inline void upd(int l,int r,T a,T d){
      if(l>r)return;
      add(l,a),add(l+1,d-a);
      add(r+1,-(a+d*(r-l+1)));
      add(r+2,a+d*(r-l));
    }
    inline T sum(int n){
      if(n<0)return 0;
      T s=c.sum(n)*(n+1)*(n+2);
      s-=(n*2+3)*c1.sum(n),s+=c2.sum(n);
      return s/2;
    }
}; // 维护区间加等差数列 & 区间和
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,p,c=0; cin>>n>>p;
  vector<int> h(n),w(n),v={0};
  for(auto &i:h)cin>>i,v.emplace_back(i);
  iota(w.begin(),w.end(),0);
  sort(w.begin(),w.end(),[&](int x,int y){
    return h[x]>h[y];
  });
  for(int i=1;i<=n;i++)
    v.emplace_back(p/i+!!(p%i)-1);
  sort(v.begin(),v.end(),greater<>());
  v.erase(unique(v.begin(),v.end()),v.end());
  // 预处理出所有分界点，存储在 v 中并去重
  set<pii> s; // 维护连续段
  arithmetic_fenwick_tree<int> t(n);
  auto add=[&](int k){t.upd(0,k-1,k,-1);};
  auto del=[&](int k){t.upd(0,k-1,-k,1);};
  for(int i=0,l=1,x=0;i+1<v.size();i++){
    while(l<=n&&l*v[i]<p)l++;
    while(x<n&&h[w[x]]>v[i+1]){
      auto it=s.lower_bound(make_pair(w[x],0));
      if(it!=s.end()&&it->first==w[x]+1){
        auto [l,r]=*it;
        del(r-l+1),add(r-l+2);
        s.erase(it),s.emplace(w[x],r);
      }
      else s.emplace(w[x],w[x]),add(1);
      it=s.lower_bound(make_pair(w[x],0));
      if(it!=s.begin()&&prev(it)->second==w[x]-1){
        auto [l1,r1]=*prev(it); auto [l2,r2]=*it;
        del(r1-l1+1),del(r2-l2+1),add(r2-l1+1);
        it=s.erase(--it),s.erase(it),s.emplace(l1,r2);
      }
      x++;
    }
    c+=(v[i]-v[i+1])*(t.sum(n-1)-t.sum(l-2));
  }
  cout<<c<<endl;
  return 0;
}