题解：CF2042D Recommendations

· · 题解

题意可以被描述为：给定 n 个区间，求每个区间的母区间的交集的长度再减掉自身的长度。

先按照左端点为第一关键字升序排序。

这样，对于排序后第 i 个区间，前面的区间中如果有右端点大于 i 的右端点的区间就是第 i 个区间的母区间。

贡献有两部分：第 i 个区间的左边和右边。

但是请注意，不管是哪部分的贡献，都建立在一个前提上：母区间的交集。

第一部分的贡献（左边）怎么求？我们需要找到一个最大的母区间左端点。

第二部分的贡献（右边）怎么求？我们需要找到一个最小的母区间右端点。

这两部分的贡献有多种求法。

  1. 可以线段树二分：先离散化，记录下前缀每个数的数值的前缀和，出现次数的前缀和，这可能需要开两颗线段树。
  2. 树状数组：先离散化，这种做法单次询问要 O(\log^2n)，不过树状数组常数小，实测和线段树没什么区别。
  3. 观察到每次查询的是一段前缀，那就可以直接开 set 维护，用 STL 自带的二分单次查询 O(\log n)。比较好写。

代码量很不小。

复杂度 O(n\log n+q\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
multiset<int> s;
int n,ans[N];
struct str{
    int l,r,id;
}a[N];
struct tee{
    int num,id,minn;
}tree[N<<2];
bool cmp(str a,str b){
    if(a.l == b.l) return a.r > b.r;
    else return a.l < b.l;
}
inline int ls(int p){return p << 1;}
inline int rs(int p){return (p << 1) | 1;}
void Push_up(int p){
    tree[p].num = max(tree[ls(p)].num,tree[rs(p)].num);
    tree[p].minn = min(tree[ls(p)].minn,tree[rs(p)].minn);
}
void Build(int s,int t,int p){
    if(s == t){
        tree[p].minn = a[s].r;
        tree[p].num = a[s].r;
        tree[p].id = a[s].id;
        return;
    }
    int mid = s+((t-s)>>1);
    Build(s,mid,ls(p));
    Build(mid+1,t,rs(p));
    Push_up(p);
}
tee Getnum(int l,int r,int s,int t,int p){
    if(l <= s && t <= r) return tree[p];
    int mid = s+((t-s)>>1);
    tee maxn = {0,0};
    if(l <= mid){
        tee res = Getnum(l,r,s,mid,ls(p));
        if(res.num > maxn.num) maxn = res;
    }
    if(r > mid){
        tee res = Getnum(l,r,mid+1,t,rs(p));
        if(res.num > maxn.num) maxn = res;
    }
    return maxn;
}
int Getmin(int l,int r,int s,int t,int p){
    if(l <= s && t <= r) return tree[p].minn;
    int mid = s+((t-s)>>1),res = 1e9+10;
    if(l <= mid) res = min(res,Getmin(l,r,s,mid,ls(p)));
    if(r > mid)  res = min(res,Getmin(l,r,mid+1,t,rs(p)));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--){
        cin>>n; s.clear();
        for(int i = 1;i<=n+10;i++) ans[i] = 0,a[i].l = a[i].r = a[i].id = 0;
        for(int i = 1;i<=(n<<2)+10;i++)
            tree[i].num = tree[i].id = 0,tree[i].minn = 0;
        for(int i = 1;i<=n;i++){
            cin>>a[i].l>>a[i].r;
            a[i].id = i;
        }
        sort(a+1,a+n+1,cmp);
        Build(1,n,1);
        s.insert(a[1].r);
        for(int i = 2;i<=n;i++){
            if(i < n && a[i].l == a[i+1].l && a[i].r == a[i+1].r){
                s.insert(a[i].r);
                continue;
            }
            int l = 1,r = i-1,tmp = i;
            while(l <= r){
                int mid = l+((r-l)>>1);
                tee res = Getnum(mid,i-1,1,n,1);
                if(res.num >= a[i].r) tmp = mid,l = mid+1;
                else r = mid-1;
            }
            ans[a[i].id] = a[i].l - a[tmp].l;
            auto p = s.lower_bound(a[i].r);
            if(p != s.end()) ans[a[i].id] += *p - a[i].r;
            s.insert(a[i].r);
        }
        for(int i = 1;i<=n;i++)
            cout<<ans[i]<<'\n';
    }

    return 0;
}