二维偏序

  • 题意: 每个物品有两个参数(x,y),问\(x_i > x_j 且 y_i > y_j\)成立的\(j\)有多少个.
  • 思路: 二维偏序,先对x进行排序,对y离散化,从后到前循环,对点i,树状数组求当前有多少个y比y_i小的,若小于n-i,则说明后面存在y比他大的,且后面的一定x比他大,所以当前这个点能贡献一次答案,然后再在y_i添加一次树状数组
#include<cstring>
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5+10;
struct node{
    int x,y;
}a[N];
int n,w[N];
struct bit{
    int a[N];
    void update(int x,int pos){
        for(int i=pos;i<=n;i+=i&(-i))
            a[i] += x;
    }
    int sum(int pos){
        int res = 0;
        for(int i=pos;i;i-=i&(-i))
            res += a[i];
        return res;
    }
    int query(int l,int r){
        return sum(r) - sum(l-1);
    }
}bt;
int cmp(node a,node b){
    return a.x < b.x;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)   scanf("%d%d",&a[i].x,&a[i].y),w[i] = a[i].y;
    sort(w+1,w+1+n);
    int t = unique(w+1,w+1+n)-w-1;
    for(int i=1;i<=n;++i){
        a[i].y = lower_bound(w+1,w+t+1,a[i].y) - w;
    }
    sort(a+1,a+1+n,cmp);
    int ans = 0;
    for(int i=n;i>=1;--i){
        int d = bt.sum(a[i].y);
        if(n-i-d!=0)    ans++;
        bt.update(1,a[i].y);
    }
    printf("%d\n",ans);
    return 0;
}

题目

原文地址:https://www.cnblogs.com/xxrlz/p/11644895.html

时间: 10-09

二维偏序的相关文章

【贪心】【二维偏序】【权值分块】bzoj1691 [Usaco2007 Dec]挑剔的美食家

既然题目中的要求满足二维偏序,那么我们很自然地想到将所有东西(草和牛)都读进来之后,对一维(美味度)排序,然后在另一维(价值)中取当前最小的. 于是,Splay.mutiset.权值分块什么的都支持查询后继呢. 1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int Num,CH[12],f,c; 6 inline void R(int &x)

【BZOJ1109】[POI2007]堆积木Klo 二维偏序

[BZOJ1109][POI2007]堆积木Klo Description Mary在她的生日礼物中有一些积木.那些积木都是相同大小的立方体.每个积木上面都有一个数.Mary用他的所有积木垒了一个高塔.妈妈告诉Mary游戏的目的是建一个塔,使得最多的积木在正确的位置.一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置.Mary决定从现有的高塔中移走一些,使得有最多的积木在正确的位置.请你告诉Mary她应该移走哪些积木. Input 第一行为一个数n,表示高塔的初始高度.第二行包含n个数

51nod 1376: 最长递增子序列的数量(二维偏序+cdq分治)

1376 最长递增子序列的数量 Time Limit: 1 Sec Memory Limit: 128MB 分值: 160 难度:6级算法题 Description 数组A包含N个整数(可能包含相同的值).设S为A的子序列且S中的元素是递增的,则S为A的递增子序列.如果S的长度是所有递增子序列中最长的,则称S为A的最长递增子序列(LIS).A的LIS可能有很多个.例如A为:{1 3 2 0 4},1 3 4,1 2 4均为A的LIS.给出数组A,求A的LIS有多少个.由于数量很大,输出Mod 1

[luogu4479][BJWC2018]第k大斜率【二维偏序+二分+离散化+树状数组】

传送门 https://www.luogu.org/problemnew/show/P4479 题目描述 在平面直角坐标系上,有 n 个不同的点.任意两个不同的点确定了一条直线.请求出所有斜率存在的直线按斜率从大到小排序后,第 k 条直线的斜率为多少. 为了避免精度误差,请输出斜率向下取整后的结果.(例如: ?1.5? = 1 , ??1.5? = ?2 ) 分析 一开始打了一个暴力,10分后来改着改着成了30分,浮点误差. 正解其实很简单,我们首先逆向思考一下,如果我们假设已经有了斜率k. 如

Codeforces Round #625 Div1 C,二维偏序,排序+线段树

题目 题意: 有若干武器A,攻击力A1,费用A2, 有若干铠甲B,防御力B1,费用B2, 有若干怪兽M,攻击力M1,防御力M2,奖励M3 你可以选择一把武器,一个铠甲,打败所有攻击和防御都严格小的怪兽,问最大收益. 思路: 典型的二维偏序问题,把攻击和防御想象成二维的坐标轴,我们要找到的其实就是一个矩形里(0,0)~(x,y)里收益-这个矩形的花费的最大值.我们可以排序一维,另一维用线段树维护,枚举的时候往里面加怪兽就好. 代码: #include <bits/stdc++.h> using

CF1321-World of Darkraft: Battle for Azathoth (线段树+二维偏序)

题意: 题目大致意思是给你n把武器,m件防具,p个怪兽,接下来n行每行告诉你该武器的攻击力和花费, 接下来m行告诉你该防具的防御力和花费,然后p行每行告诉你这个怪兽的攻击力,防御力以及打败这个 怪兽可以获得的金钱数,当你的攻击力大于怪兽的防御力,并且你的防御力大于怪兽的攻击力时,你可 以打败这个怪兽.你必须至少购买1件武器和1件防具,问你最多可以获得多少钱. 链接:https://codeforces.com/contest/1321/problem/E 思路: 看了大神的题解,第一次知道二维偏

CF1221F Choose a Square(二维偏序)

由于y=x,我们可以将点对称过来,以便(x,y)(x<y) 考虑选取正方形(a,a,b,b),点集则为\((a\le x\le y\le b)\),相当于二维数点 将点按x降序,y升序排列,线段树先存"-坐标",以便统计\((a,b)\)时直接线段树查询最大值再加b即可 原文地址:https://www.cnblogs.com/y2823774827y/p/11629629.html

HDU 1069 Monkey and Banana(二维偏序LIS的应用)

---恢复内容开始--- Monkey and Banana Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13003    Accepted Submission(s): 6843 Problem Description A group of researchers are designing an experiment to te

BZOJ 1537 二维偏序

1 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <algorithm> 6 #include <map> 7 using namespace std; 8 const int Maxn=100100; 9 int n,m,k,c[Maxn],F[Maxn]; 10 map<int,int> M; 11 struct Info{int