競プロ典型90問 066 O(NlogN)

90-typical-problems-066.cpp

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

/*******************************************************************************************
 * For i<j, x in the i-th interval [Li,Ri], and y in the j-th interval [Lj,Rj]
 * the contribution of (x,y) to the answer is 1/(Ri-Li+1)*(1/(Rj-Lj+1)) if x>y and 0 if x<=y
 * Note that 1/(Ri-Li+1) only depends on i, and 1/(Rj-Lj+1) only depends on j
 *
 * So, for each y, we add 1/(Rj-Lj+1) from all j-th intervals where i<j, and call it contrib[y]
 * Then the total contribution related to the i-th interval is:
 * for(int x=Li;x<=Ri;x++)
 *   for(int y=0;y<x;y++)
 *      total_contrib+=1/(Ri-Li+1)*contrib[y]
 * which is the sum of perfix sums over an interval. A segment tree can be used to efficiently
 * compute this as well as efficiently add and remove intervals. Coordinate compression is also
 * needed when Li,Ri are large.
 *
 * Overall complexity: O(NlogN)
 *******************************************************************************************/

struct Interval{
  int len;
  // sum=a[0]+a[1]+...+a[len-1]
  // integ=(a[0])+(a[0]+a[1])+...+(a[0]+a[1]+...+a[len-1])
  double sum,integ;
  inline double integ_excl(){
    return integ-sum;
  }
};

Interval interval_merge(Interval a,Interval b){
  return {a.len+b.len,a.sum+b.sum,a.integ+a.sum*b.len+b.integ};
}

Interval zero(){
  return {0,0,0};
}

Interval apply(double x,Interval a){
  a.sum+=x*a.len;
  a.integ+=x*(1ll*a.len*(a.len+1)/2);
  return a;
}

double compose(double x,double y){
  return x+y;
}

double identity(){
  return 0;
}

int main(){
  int n;
  cin>>n;
  vector<pair<int,int>> range(n);
  vector<int> bound(n*2);
  for(int i=0;i<n;i++){
    int l,r;
    cin>>l>>r;
    l--;
    bound[i*2]=l;
    bound[i*2+1]=r;
    range[i]={l,r};
  }
  // coordinate compression
  sort(bound.begin(),bound.end());
  auto last=unique(bound.begin(),bound.end());
  bound.erase(last,bound.end());
  for(auto &rng:range){
    rng.first=lower_bound(bound.begin(),bound.end(),rng.first)-bound.begin();
    rng.second=lower_bound(bound.begin(),bound.end(),rng.second)-bound.begin();
  }
  // initialize the segment tree
  vector<Interval> init(bound.size()-1);
  for(int i=1;i<bound.size();i++)
    init[i-1]={bound[i]-bound[i-1],0,0};
  lazy_segtree<Interval,interval_merge,zero,double,apply,compose,identity> seg(init);
  // add all intervals to the segment tree
  for(auto &rng:range){
    int l,r;
    tie(l,r)=rng;
    int len=bound[r]-bound[l];
    seg.apply(l,r,1.0/len);
  }
  double ans=0;
  // for each interval
  for(auto &rng:range){
    int l,r;
    tie(l,r)=rng;
    int len=bound[r]-bound[l];
    // remove itself from the segment tree
    seg.apply(l,r,-1.0/len);
    // compute the contribution of itself from all intervals after it
    // (i.e. all intervals still in the segment tree)
    ans+=(seg.prod(0,r).integ_excl()-seg.prod(0,l).integ_excl())/len;
  }
  cout<<setprecision(15)<<ans<<endl;
}