CF竞赛题目讲解_CF1139F(树状数组+树状数组+顺序扫描)

https://codeforces.com/contest/1139/problem/F

对于每个人， income inc为x，pref为y；

对于每道菜，price p和 standard s， beauty b

It is guaranteed that for all integers i from 1 to n, the following condition holds: pi≤si.

于是根据题意有

 pi≤incj≤si.

 和

|bi−prefj|≤(incj−pi) 

即

p[i]<=x<=s[i],  

 和

p[i]+b[i]<=x+y

p[i]−b[i]<=x−y

把所有出现的点都离散化一下，排序去重，然后开始扫x轴

对于p[i]+b[i]和p[i]-b[i]这两个函数，分别用2个树状数组去维护合法菜碟的个数