二分，递归，分治！！！

题意

集训队内的氛围是相当和谐的，如果某个问题上双方产生了争执会通过智力或是武力来解决问题。

集训队内的每个人有各自的武力值和智力值，如果一个队员x的智力值和武力值均大于等于另一个队员y，则x与y的争执中x必定获胜（保证没有两个人武力值和智力值均相同）

队长想知道队内有多少队员能恰好在争执中击败一个其他队员，又有多少队员能恰好在争执中击败两个其他队员，又有多少队员能恰好在争执中击败三个其他队员。。。。
由于每个数都问一遍太麻烦了，你只需要对0-（N-1）的每一个数都输出一遍就好啦
输入

输入的第一行包括了集训队成员的数量N (1<=N<=15000)，下面N行描述了每个队员的武力值a和智力值b(0<=a,b<=32000)。输入队员按智力值排序，智力值相同则按武力值排序
输出

输出包括N行，每行一个数字。第一行为能恰好在争执中击败0个其他队员的队员数量，第二行为能恰好在争执中击败1个其他队员的队员数量，以此类推，最后一行为能恰好在争执中击败N-1个其他队员的队员数量

分析

这题究竟让我们干什么？
就是给我们n个坐标，让我们找每一个坐标可以包含的坐标数，然后统计，最后输出正好包含0个坐标的有多少
正好包含1个坐标的有多少，正好包含2个坐标的有多少，，，，，，，，，
OK,这种题我们凭借直觉知道我们是肯定要按照x或y轴其中一个进行排序的。
假设我们对x轴排序这样我们就只需比较，y轴就行了。
现在，我们按照x轴从小到大排序，如果x相等，那么按照y轴从小到大排序。
这样，在不存在两个完全一样的坐标的情况下，我们从左向右遍历，遍历到a[i]
那么a[i]所能包含的坐标一定在i之前，也就是我们已经遍历过的坐标!!!!!!

那么自然而然，我们可以这样做：
创建一个容器b
我们从左向右遍历，被遍历一个都push到容器b中
在此之前，我们先找到容器b中y坐标小于等于我目前遍历到的坐标的wy坐标的数量
这个数量就是我能包含的坐标数！

其实，看看题目，出题人都已经包我们排好序了，我们读取进来其实只需对y坐标所在的数组进行处理了，x轴坐标所在的数组根本不用去管。

这个算法的时间复杂度是O(n^2)
显然我们是无法接受的，下面我们要优化。
很容易想到，利用二分查找进行优化，我们对容器b进行从小到大的有序维护
在拿到a[i]时，upper_bound一下减去开头，这样我们就可以得到b中小于a[i]的数有多少个了。
得到之后，再将a[i]插入
这是看似十分正确的做法。但却是错误的！！
因为，插入也是要耗时的。。。。。。。。。如果我们选择插入耗时时间为常数的容器list
那么二分的部分就无法实现了，虽然可以进行二分查找，但是却无法通过减去开头的迭代器从而得出小于等于
a[i]的值的数目。

真是糟糕！！！！
我们不得不在采用别的思路了！！！！！！（当时的我真的很失望）

偷偷看一下标题。。“分治，递归”
我们再看我们实际要解决的问题。
对于数组： [1,1,1,2,3,42,1,3,4,1,0,4,44,5,23,42,1,5,1,3,5,78,4,6,9,3]
我们要求对于a[i]他前面有几个小于等于他的数。
整体二分！！
假设我们得出了[0,mid]中每一个元素的答案，与[mid,n]中每一个元素的答案
那么[0,mid]其实就是在[0,n]这个区间中的正确答案。
而我们在对[0,mid]中的区间排个序，对于[mid,n]中的每一个元素，向[0,mid]中去二分搜索，是否就可行了呢？
可行！！！！
需要注意的有两点：
1.如果我们对区间[l,r]实行这个算法，那么所得到答案a[i]前小于等于a[i]的数目，也是在这个区间的数目，而不会是在[0,n]大区间的数目。但是，这点不用在意，因为最终我们将会在[0,n]进行这个算法，一直相加就好了。
2.再进行排序时，我们会打乱原来数组的顺序，我们应该复制一个相同的数组，在这个数组中进行排序。(光靠口说，很难体会，建议自己编码感受)

下面代码，注意细节

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 32100;
int x[max_n];
int y[max_n];
int a[max_n];
int b[max_n];
int c[max_n];
int n;

void solve(int l,int r) {
    if (r - l <= 1)return;
    int mid = (l + r) >> 1;
    solve(l, mid);solve(mid, r);
    sort(c + l, c + mid);
    for (int i = mid;i < r;i++)
        a[i] += upper_bound(c + l, c + mid, y[i]) - c - l;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> y[i] >> x[i];
        c[i] = y[i];
    }
    solve(0,n);
    for (int i = 0;i < n;i++)b[a[i]]++;
    for (int i = 0;i < n;i++)
        cout << b[i] << endl;
}