树状数组

题意：

分析：

我们很明显便能明白：对于妹子g1,如果没有其他妹子的细心程度和热心程度都大于他的话，就说明她是1级的。
既然如此，我们不妨按照一个参数排一下序。
按照细心程度排序：[g1,g2,g3,g4,g5,g6......]
对于gi如果前面没有girl比的热心程度比她大，那么她就是一级的。
如此判断了一级的再去掉她们，然后以同样的手法判断二级的。
如此重复，最后将会得到答案。

那么接下来我们考虑如何在一次遍历中得到答案。
我们遍历到gi时，去到前面的比大小。注意，我们此时前面的所有girl都已经确定了其重要程度。
那么我们再比大小时，发现所有比当前女孩gi大的点，只有当这些女孩都在我们之前的分析中那样被去掉才能使得gi大于前面所有的女孩。
那么什么时候这些女孩都被去掉呢？这些女孩的最高级别+1！！！！！！这就是gi的重要级别

ok，我们已经找到思路了。那么接下来如何实现吧。
我们用树状数组实现。
a[i]=级别，树状数组用于记录[i,j]的最大值
这里的i和j指的是gi的热心程度。有点类似与统计排序的思想。ok?
我们从左到右遍历
看之前大于gi的热心程度的妹子的最高级别是多少，即求max([gi.热心，max])
是否？就是这样！

因为树状数组的特点，以右端为界不太好求。所以我们尝试将其便为以左端为界。
我们要找gi的前面热心程度大于gi的妹子的最大级别，那么我们不妨将热心程度重新编号
按照原来从大到小的顺序，从小到大编号，这样问题就变成了
我们要找gi的前面热心程度小于gi的妹子的最大级别。OK
接下来我们只要更新树状数组，即a[i]=gi.级别。这样更新就可以了。

树状数组进阶中！！！！！！吼吼吼！！！
##代码如下

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
struct girl{int a, b, num;};
bool cmp1(const girl& g1, const girl& g2) { return g1.a > g2.a; }
bool cmp2(const girl& g1, const girl& g2) { return g1.b > g2.b; }
const int max_n = 1e5 + 100;
int n;
girl input[max_n];
int ans[max_n];
int BIT[max_n];

void renew(int x,int val) {
    for (;x <= n;x += (x & -x))BIT[x] = max(BIT[x], val);
}

int quiry(int x) {
    int res = 0;
    for (;x;x -= (x & -x))res = max(res, BIT[x]);
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1;i <= n;i++) { cin >> input[i].a >> input[i].b; input[i].num = i; }
    sort(input + 1, input + 1 + n, cmp2);
    for (int i = 1;i <= n;i++)input[i].b = i;
    sort(input + 1, input + 1 + n, cmp1);
    for (int i = 1;i <= n;i++) { ans[input[i].num] = quiry(input[i].b) + 1;renew(input[i].b, ans[input[i].num]); }
    for (int i = 1;i <= n;i++)cout << ans[i] << endl;
}