题解：CF2042D Recommendations

题意可以被描述为：给定

n

个区间，求每个区间的母区间的交集的长度再减掉自身的长度。

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

这样，对于排序后第

i

个区间，前面的区间中如果有右端点大于

i

的右端点的区间就是第

i

个区间的母区间。

贡献有两部分：第

i

个区间的左边和右边。

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

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

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

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

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

代码量很不小。

复杂度

O(n\log n+q\log n)

。

CPP

#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;
}

题解：CF2042D Recommendations

文章操作

相关推荐

评论

题解：CF2042D Recommendations