Laptop(线段树+离散化)-白红宇

Laptop(线段树+离散化)

阅读量：5011 次

发布时间：2019-06-12

本文共 1681 字，大约阅读时间需要 5 分钟。

链接：

来源：牛客网

题目描述

FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。

但是重点在于，他非常适合ACM！并在最近的区域赛中获得了不错的成绩。

拿到奖金后FST决定买一台新笔记本，但是FST发现，在价格能承受的范围内，笔记本的内存和速度是不可兼得的。

可是，有一些笔记本是被另外一些“完虐”的，也就是内存和速度都不高于另外某一个笔记本，现在FST想统计一下有多少笔记本被“完虐”。

输入描述:

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

，S

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

⁵

,M

,S

≤10

⁹

输出描述:

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

示例1

输入

4100 700200 50050 100300 400

输出

备注:

和S

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

互不相同，S

也互不相同。 代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                const int maxn=2e5+5;typedef long long ll;using namespace std;struct node{ int l,r; int num;}tree[maxn<<2];struct node1{ int a,b; bool friend operator <(node1 x,node1 y) { return x.a>y.a; }}p[maxn];vector
                
                 v;void build(int m,int l,int r){ tree[m].l=l; tree[m].r=r; tree[m].num=0; if(l==r) { return ; } int mid=(l+r)>>1; build(m<<1,l,mid); build(m<<1|1,mid+1,r);}void update(int m,int pos,int val){ if(tree[m].l==tree[m].r&&tree[m].l==pos) { tree[m].num=val; return ; } int mid=(tree[m].l+tree[m].r)>>1; if(pos<=mid) update(m<<1,pos,val); else { update(m<<1|1,pos,val); } tree[m].num=(tree[m<<1].num+tree[m<<1|1].num);}int query(int m,int l,int r){ if(tree[m].l==l&&tree[m].r==r) { return tree[m].num; } int mid=(tree[m].l+tree[m].r)>>1; if(r<=mid) { return query(m<<1,l,r); } else if(l>mid) { return query(m<<1|1,l,r); } else { return query(m<<1,l,mid)+query(m<<1|1,mid+1,r); }} int getid(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}int main(){ int n; cin>>n; for(int t=0;t