自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:56:29，当前版本为作者最后更新于2024-03-25 14:29:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑对于一个区间 $[l_i,r_i]$，最少重叠长度为 $k_i$，怎样的区间 $[l_j,r_j]$ 可以与前者产生贡献；首先 $r_j-l_j\ge k_i$，在满足这个条件的情况下需要有 $r_j\ge l_i+k_i\land l_j\le r_i-k_i$，这里 $\land$ 表示合取，即 C++ 中的 $\mathrm{and}$。正难则反，考虑用长度 $\ge k_i$ 的区间数量减去 $r_j<l_i+k_i$ 以及 $l_j>r_i-k_i$ 的区间数量和；容易得知后两部分是不交的，可以分开计算。

统计这个数量这是一个经典的二维数点问题。直接将待处理的数组按照 $k$ 降序排序，复制一份按照 $r-l$ 排序。扫前者的同时从后者里面把满足 $r-l\ge k$ 的区间不断加入答案，用 __gnu_pbds::tree 插入元素、统计答案即可。可以参考代码实现。

放代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
typedef tuple<int,int,int,int> tpi;
int main(){
  ios::sync_with_stdio(false);
  int n,p=0; cin>>n;
  vector<tpi> a(n),b;
  for(int i=0;i<n;i++){
    auto &[l,r,k,x]=a[i]; cin>>l>>r>>k,x=i;
  }
  sort(a.begin(),a.end(),[](tpi x,tpi y){
    return get<2>(x)>get<2>(y);
  });
  b=a,sort(b.begin(),b.end(),[](tpi x,tpi y){
    return get<1>(x)-get<0>(x)>get<1>(y)-get<0>(y);
  }); // 两种排序
  tree<pii,null_type,greater<>,rb_tree_tag,tree_order_statistics_node_update> L;
  tree<pii,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> R;
  vector<int> s(n);
  for(auto [l,r,k,x]:a){
    while(p<n&&get<1>(b[p])-get<0>(b[p])>=k)
      L.insert(make_pair(get<0>(b[p]),p)),R.insert(make_pair(get<1>(b[p]),p)),p++;
    // 加入可能成为答案的元素
    s[x]=L.size()-R.order_of_key(make_pair(l+k,0))-L.order_of_key(make_pair(r-k,n));
    // 使用 order_of_key 查排名，进行统计
  }
  for(int i:s)cout<<i-1<<'\n';
  return 0;
}