解题思路

这个题目需要计算每头奶牛被多少头其他奶牛"强"于它。根据题目定义，一头奶牛i比另一头奶牛j强的条件是：

1. Si ≤ Sj
2. Ej ≤ Ei
3. Ei - Si > Ej - Sj

给定的代码使用了树状数组(Binary Indexed Tree)来高效解决这个问题。下面是详细的解题思路：

1. 输入处理：

   • 读取奶牛数量n
   • 读取每头奶牛的区间[S,E]，存储为结构体数组，并做+1处理（可能是为了避免0下标问题）
   • 给每头奶牛分配唯一id

2. 排序处理：

   • 将奶牛按照区间终点E降序排序，如果E相同则按S升序排序
   • 这样排序后可以保证在后续处理中，当前奶牛的E总是小于等于前面处理过的奶牛的E

3. 树状数组的使用：

   • 初始化树状数组tr用于统计
   • 从前往后处理排序后的奶牛：
     • 如果当前奶牛区间与前一个完全相同，则直接复制前一个的结果
     • 否则，使用树状数组查询比当前奶牛S小的数量（即满足Si ≤ Sj的奶牛数量）
   • 将当前奶牛的S值更新到树状数组中

4. 输出结果：

   • 按照原始id顺序输出每头奶牛的结果

关键点说明

1. 排序策略：

   • 按E降序排序是为了保证在处理当前奶牛时，前面处理过的奶牛的E都≥当前E
   • 这样在查询时只需要考虑S的关系即可

2. 树状数组的作用：

   • 用于高效统计前缀和（比当前S小的数量）
   • 更新和查询的时间复杂度都是O(log n)

3. 去重处理：

   • 当遇到相同区间时直接复制前一个结果，避免重复计算

4. 坐标调整：

   • 将S和E都+1，可能是为了避免树状数组处理0下标的问题

算法复杂度

• 时间复杂度：O(n log n)（排序O(n log n)，树状数组操作O(n log n)）
• 空间复杂度：O(n)

这个解法巧妙地利用排序和树状数组的结合，将原本需要O(n²)时间的问题优化到了O(n log n)时间，能够高效处理大规模数据。

标程

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=100010;
int tr[maxn], ans[maxn];
struct point{
	int x, y, id;
	bool operator < (const point &p)const{
		if(y!=p.y) return y>p.y;
		return x<p.x;
	}
}p[maxn];
int lowbit(int x){
	return x&(-x);
}
void updata(int x){
	while(x<maxn){
		tr[x]++;
		x+=lowbit(x);
	}
}
int getsum(int x){
	int s=0;
	while(x>0){
		s+=tr[x];
		x-=lowbit(x);
	}
	return s;
}
int main(){
	int n;
	while(scanf("%d", &n), n){
		int x, y;
		memset(tr, 0, sizeof(tr));
		for(int i=1; i<=n; i++){
			scanf("%d%d", &p[i].x, &p[i].y);
			p[i].x++;
			p[i].y++;
			p[i].id=i;
		}
		p[0].x=-1, p[0].y=-1;
		sort(p+1, p+n+1);
		memset(ans, 0, sizeof(ans));
		for(int i=1; i<=n; i++){
			if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y) ans[p[i].id]=ans[p[i-1].id];
			else ans[p[i].id]=getsum(p[i].x);
			updata(p[i].x);
		}
		for(int i=1; i<=n; i++){
			printf("%d%c", ans[i], i==n?'\n':' ');
		}
	}
	return 0;
}