博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj2481树状数组解二维偏序
阅读量:4676 次
发布时间:2019-06-09

本文共 1242 字,大约阅读时间需要 4 分钟。

按区间r降序排列,r相同按照l升序排列,两个区间相同时特判一下即可

/*给定n个闭区间[l,r],如果对区间[li,ri],[lj,rj]来说,有区间j严格包含(两个边界不能同时重合)在区间i内,那么区间i大于区间j问区间有多少个区间大于区间i读入所有的区间,按r降序,l升序然后按顺序访问每个区间,*/#include
#include
#include
#include
using namespace std;#define maxn 100010struct node{ int l,r,id; bool operator<(const node & a)const { if(r==a.r) return l
a.r; }}inv[maxn];int n,ans[maxn],bit[maxn];void add(int x){ for(int i=x;i<=n;i+=i&-i) bit[i]+=1;}int query(int x){ int res=0; for(int i=x;i;i-=i&-i) res+=bit[i]; return res;}int main(){ while(scanf("%d",&n),n){ memset(bit,0,sizeof bit); for(int i=1;i<=n;i++){ scanf("%d%d",&inv[i].l,&inv[i].r); inv[i].l++;inv[i].r++; inv[i].id=i; } sort(inv+1,inv+1+n); memset(ans,0,sizeof ans); inv[0].l=-1;inv[0].r=-1; for(int i=1;i<=n;i++){ if(inv[i].l==inv[i-1].l && inv[i].r==inv[i-1].r) ans[inv[i].id]=ans[inv[i-1].id]; else ans[inv[i].id]=query(inv[i].l); add(inv[i].l); } for(int i=1;i

 

转载于:https://www.cnblogs.com/zsben991126/p/10079688.html

你可能感兴趣的文章
MongoDB 3.2 从安装到使用。
查看>>
完全卸载oracle11g步骤
查看>>
再次说搜索
查看>>
spring测试
查看>>
c++ mfc 曲线图像的实现资料网址
查看>>
JetBrains系列WebStorm等中文输入法无法跟随光标的问题的解决办法
查看>>
解决Admob Banner首次展示不显示的问题
查看>>
系列6:进程间通信
查看>>
日志配置
查看>>
第四周作业 简单地邮件发送实现
查看>>
[转载]读史记札记26:容人岂皆有雅量
查看>>
表达式计算(模拟)
查看>>
Unity3D 游戏引擎之实现平面多点触摸(二)
查看>>
【Xilinx-Petalinux学习】-02-建立PetaLinux工程
查看>>
TeX中的引号
查看>>
Python 模块(module)
查看>>
region实现大纲效果
查看>>
day1
查看>>
[No0000B5]C# 类型基础 值类型和引用类型 及其 对象判等 深入研究1
查看>>
AJAX JSONP源码实现(原理解析)
查看>>