扫描线+树状数组——cf1191F
2024-08-24 01:34:08
把所有点离散化,虚构一根扫描线从上往下扫,每行的点从左往右算贡献,开一个树状数组维护每个离散化后的x坐标是否已经有点
扫描到一个点时,先把这个点更新到树状数组里,每个点的贡献是它左边的所有点数*到它相邻右边点之间的所有点数
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define maxn 200005
struct Node {int x,y;}p[maxn];
int cmp(Node a,Node b){
if(a.y==b.y)return a.x<b.x;
return a.y>b.y;
}
int n,m;
vector<int>x,y; int bit[maxn],f[maxn];
void update(int x){
while(x<=m){
bit[x]++;
x+=x&-x;
}
}
int query(int x){
int res=;
while(x){
res+=bit[x];
x-=x&-x;
}
return res;
} int main(){
cin>>n;
for(int i=;i<=n;i++){
cin>>p[i].x>>p[i].y;
x.push_back(p[i].x);
}
sort(p+,p++n,cmp);
sort(x.begin(),x.end());
x.erase(unique(x.begin(),x.end()),x.end());
m=x.size(); long long ans=;
for(int i=;i<=n;i++){
int pos,R;
if(i==n || p[i+].y!=p[i].y)
R=m; else R=lower_bound(x.begin(),x.end(),p[i+].x)-x.begin()+-;
pos=lower_bound(x.begin(),x.end(),p[i].x)-x.begin()+;//p[i]所在位置
if(!f[pos])
update(pos),f[pos]=;
ans+=(long long)query(pos)*(query(R)-query(pos-));
}
cout<<ans<<endl;
}
最新文章
- Oracle Dataguard之failover
- Java内存回收机制
- HTML5音乐播放器(最新升级改造加强版)
- phpcmsV9.5.8整合百度编辑器Ueditor1.4.3教程
- stringbuffer与stringbuilder与String
- paip. 解决java程序不能自动退出
- DIV实现纵向滚动条overflow-y
- 15_Python模块化编程_Python编程之路
- Pandas基本操作
- firewall配置
- AXI Traffic Generator 生成axi-lite axi4 axis 的IP
- (转)linux下查看已安装的软件与卸载
- 2019-03-01-day002-基础编码
- sourceInsight与IAR的同步
- 剑指offer十五之反转链表
- Samba共享及自动挂载测试
- C struct的内存对齐
- 开源介绍:Google Guava、Google Guice、Joda-Time
- C 标准库 - string.h之strncpy使用
- Swift &; Unicode
热门文章
- windows线程函数必须为全局函数或者静态函数(转)
- rest framework之路由组件
- CSIC_716_20191217【事务、视图、触发器、存储过程、索引】
- 影响Acorn for Mac图像打印质量的因素有什么?怎样处理这些因素才能得到打印效果最佳的图像?
- 【leetcode】958. Check Completeness of a Binary Tree
- Delphi ADOQuery的 DisableControls 和 EnableControls方法
- security安全框架 配置
- 学习android文档 -- Adding the Action Bar
- C++之string面试问题
- springboot使用自带连接池连接postgre