题解 AT1279 【How are you?】
TRZ_2007
2020-10-18 14:05:27
- 题目传送门：[AT1279 How are you?](https://www.luogu.com.cn/problem/AT1279)
# Description
给你 $n$ 段区间，求对于一个区间来说，**左端点比它大且与它有交**的区间个数。
$n \le 10^5$。
# Solution
观察到 $n \le 10^5$ ，很自然就会想到 $\mathcal{O(n)}$ 或者 $\mathcal{O(n\log n)}$ 的做法，这题要求区间的交，因此我们需要对所有的区间进行**左端点从小到大**排序，然后计算出**第一个左端点比它小**的区间的位置，减去该区间位置即为所求。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct node {
int x,y,id;
}a[N];
int n,f[N];
bool cmp1(node u,node v) {
if(u.x == v.x) return u.y < v.y;
return u.x < v.x;
}
bool cmp2(node u,node v) {
return u.id < v.id;
}
int find(int x) {
int l = 1,r = n,ans;
while(l <= r) {
int mid = (l + r) >> 1;
if(a[mid].x <= x) {
l = mid + 1;
ans = mid;
}else {
r = mid - 1;
}
}
return ans;
}
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;i++) {
scanf("%d %d",&a[i].x,&a[i].y);
a[i].id = i;
}
sort(a + 1,a + n + 1,cmp1);
for(int i = 1;i <= n;i++) {
int t = find(a[i].y);
f[a[i].id] = t - i;
}
sort(a + 1,a + n + 1,cmp2);
for(int i = 1;i <= n;i++) {
printf("%d\n",f[i]);
}
return 0;
}
```