牛客网 牛客练习赛4 A.Laptop-二维偏序+离散化+树状数组

A.Laptop

链接：https://ac.nowcoder.com/acm/contest/16/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。
但是重点在于，他非常适合ACM！并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本，但是FST发现，在价格能承受的范围内，笔记本的内存和速度是不可兼得的。
可是，有一些笔记本是被另外一些“完虐”的，也就是内存和速度都不高于另外某一个笔记本，现在FST想统计一下有多少笔记本被“完虐”。

输入描述:

第一行一个正整数n，
表示笔记本的数量。接下来n行，每行两个正整数M

，S

表示这款笔记本的内存和速度。
n≤10

,M

,S

≤10

输出描述:

一行，一个正整数，表示被完虐的笔记本数。

示例1

输入

4

100 700

200 500

50 100

300 400

输出

1

备注:

M

和S

都是越大越优。
数据保证M

互不相同，S

也互不相同。

二维偏序，一种思想，按照某一位进行排序，从而减少一维，然后对剩下的维度进行操作。

这道题题意就是找有多少笔记本的s和w性能都比一个别的笔记本小。

通过对s进行离散化然后排序，再对w进行树状数组的维护就可以了。

代码：

 //A-二维偏序+树状数组

 /*

 二维偏序，就是一个思想，可以用树状数组实现。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int w[maxn],sum[maxn];

 int n;

 struct node{

     int x,y;

 }a[maxn];

 bool cmp(node a,node b)

 {

     return a.x<b.x;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 int query(int n)

 {

     int ans=;

     for(int i=n;i>;i-=lowbit(i)){

         ans+=sum[i];

     }

     return ans;

 }

 void add(int x)

 {

     for(int i=x;i<=n;i+=lowbit(i)){

         sum[i]++;

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d%d",&a[i].x,&a[i].y);

         w[i]=a[i].y;

     }

     sort(w+,w++n);

     int d=unique(w+,w++n)-(w+);

     for(int i=;i<=n;i++){

         a[i].y=lower_bound(w+,w++d,a[i].y)-w;

     }

     sort(a+,a++n,cmp);

     int ans=;

     for(int i=n;i>;i--){

         int cnt=query(a[i].y);

         if(n-i-cnt!=) ans++;//n-i是找比当前i大的，然后再减去cnt是比当前i小的，最后就是都比当前的大的

         add(a[i].y);

     }

     printf("%d\n",ans);

 }