You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.
Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 10e9 ≤ li < ri ≤ 10e9) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Output
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
题意:给你n个区间问你每个区间包含了几个小区间,这些区间没有相交。
求区间个数与线段树求逆序对方法差不多,先按右区间排序,再利用求逆序数的思想。还有由于区间数比较大但区间的个数少,要离散化一下。
#include <iostream> #include <cstring> #include <algorithm> #include <map> using namespace std; const int M = 2e5 + 10; struct ss { int x , y , num; }s[M]; int m[M << 1] , ans[M << 1]; bool cmp(ss a , ss b) { return a.y < b.y; } bool cmp1(ss a , ss b) { return a.num < b.num; } struct TnT { int l , r , sum; }T1[M << 4] , T2[M << 4]; void build(TnT T[] , int l , int r , int p) { int mid = (l + r) >> 1; T[p].l = l , T[p].r = r , T[p].sum = 0; if(T[p].l == T[p].r) { return ; } build(T , l , mid , p << 1); build(T , mid + 1 , r , (p << 1) | 1); } void updata(TnT T[] , int pos , int p) { int mid =(T[p].l + T[p].r) >> 1; if(T[p].l == T[p].r && T[p].l == pos) { T[p].sum++; return ; } if(mid >= pos) { updata(T , pos , p << 1); } else { updata(T , pos , (p << 1) | 1); } T[p].sum = T[p << 1].sum + T[(p << 1) | 1].sum; } int query(TnT T[] , int l , int r , int p) { int mid = (T[p].l + T[p].r) >> 1; if(T[p].l == l && T[p].r == r) { return T[p].sum; } if(mid < l) { return query(T , l , r , (p << 1) | 1); } else if(mid >= r) { return query(T , l , r , p << 1); } else { return query(T , l , mid , p << 1) + query(T , mid + 1 , r , (p << 1) | 1); } } int main() { int n; while(cin >> n) { int MAX = 0; map mp; int cnt = 0; memset(s , 0 , sizeof(s)); for(int i = 0 ; i < n ; i++) { cin >> s[i].x >> s[i].y; m[++cnt] = s[i].x; m[++cnt] = s[i].y; s[i].num = i; MAX = max(MAX , s[i].y); } sort(m + 1 , m + cnt + 1); for(int i = 1 ; i <= cnt ; i++) { mp[m[i]] = i; } build(T1 , 1 , cnt , 1); build(T2 , 1 , cnt , 1); sort(s , s + n , cmp); for(int i = 0 ; i < n ; i++) { updata(T1 , mp[s[i].y] , 1); updata(T2 , mp[s[i].x] , 1); ans[s[i].num] = min(query(T1 , 1 , mp[s[i].y] - 1 , 1) , query(T2 , mp[s[i].x] + 1 , cnt , 1)); } for(int i = 0 ; i < n ; i++) { cout << ans[i] << endl; } } return 0; }