二维偏序

  • 题意: 每个物品有两个参数(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

二维偏序的相关文章

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

bzoj3262: 陌上花开 二维树状数组

众所周知三维偏序可以树套树或者cdq 然后我就写了二维离散化+二维树状数组 然后被cdq艹飞了(ToT) #include<cstdio> #include<algorithm> #define N 100005 #define J i+(i&-i) #define F lower_bound #define G upper_bound using namespace std; struct io_t{ operator int(){ int x; scanf("

二维码扫码积分系统定制开发

微信积分系统 二维码扫码积分系统定制开发找丽姐[158.1816.6626/电微]二维码营销模式系统定制开发 微信扫二维码营销系统开发 扫码领积分系统开发 一.如何实现扫二维码领红包功能? 1.使用扫描二维码领取红包对活动进行设置,包括红包数量.红包金额.促销地区.中奖概率等. 2.将生成的二维码赋到商品上面并赋涂层,一方面可以起到保证二维码的一次性,另一方面也可以引起消费者的好奇心. 3.通过手机微信打开扫一扫,扫码商品二维码关注公众号并领取红包,如果参与分享还可以获得抽奖的机会. 二.微信扫

微信生成二维码 只需一个网址即刻 还有jquery生成二维码

<div class="orderDetails-info"> <img src="http://qr.topscan.com/api.php?text=http://123.net/index.php?s=/Home/Index/yanzheng/mai/{$dange.id}" style="width: 5rem; margin-bottom: 1rem;" > </div> http://qr.tops

家电二维码售后服务平台系统开发

家电二维码售后服务平台系统开发,家电二维码售后系统开发,小吴183.2071.6434微电,家电二维码售后软件开发,家电二维码售后平台开发. 互联网平台的节点有两大类型:第一基数节点,也就是弱连接的节点,其规模要大,越大越好,互联网的价值与节点数的平比成正比.第二活跃节点,也就是强连接的节点,其能量要强,越强越好,互联网的价值与其强度成正比. 一.家电维修行业"维修黑幕"层出不穷 记者从一位从事家电维修人士那里了解到,目前行业公认当前家电维修行业有陷阱,"维修黑幕"

微信小程序(4)--二维码窗口

微信小程序二维码窗口: <view class="btn" bindtap="powerDrawer" data-statu="open">button</view> <!--mask--> <view class="drawer_screen" bindtap="powerDrawer" data-statu="close" wx:if=&qu

微信服务器与项目服务器的交互(关注功能、微信扫描带参数二维码)

<?php /** * wechat php test */ //define your token define("TOKEN", "txtj"); $wechatObj = new wechatCallbackapiTest(); if (isset($_GET['echostr'])) { $wechatObj->valid(); }else{ $wechatObj->responseMsg(); } class wechatCallback

14-高效求最长公共子序列(二维数组存不下)

/*                                   See LCS again时间限制:1000 ms  |  内存限制:65535 KB难度:3 描述 There are A, B two sequences, the number of elements in the sequence is n.m; Each element in the sequence are different and less than 100000. Calculate the length

【二维树状数组】See you~

https://www.bnuoj.com/v3/contest_show.php?cid=9148#problem/F [题意] 给定一个矩阵,每个格子的初始值为1.现在可以对矩阵有四种操作: A x y n1 :给格点(x,y)的值加n1 D x y n1: 给格点(x,y)的值减n1,如果现在格点的值不够n1,把格点置0 M x1 y1 x2 y2:(x1,y1)移动给(x2,y2)n1个 S x1 y1 x2 y2 查询子矩阵的和 [思路] 当然是二维树状数组 但是一定要注意:lowbi