把所有点离散化,虚构一根扫描线从上往下扫,每行的点从左往右算贡献,开一个树状数组维护每个离散化后的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;
}

最新文章

  1. Oracle Dataguard之failover
  2. Java内存回收机制
  3. HTML5音乐播放器(最新升级改造加强版)
  4. phpcmsV9.5.8整合百度编辑器Ueditor1.4.3教程
  5. stringbuffer与stringbuilder与String
  6. paip. 解决java程序不能自动退出
  7. DIV实现纵向滚动条overflow-y
  8. 15_Python模块化编程_Python编程之路
  9. Pandas基本操作
  10. firewall配置
  11. AXI Traffic Generator 生成axi-lite axi4 axis 的IP
  12. (转)linux下查看已安装的软件与卸载
  13. 2019-03-01-day002-基础编码
  14. sourceInsight与IAR的同步
  15. 剑指offer十五之反转链表
  16. Samba共享及自动挂载测试
  17. C struct的内存对齐
  18. 开源介绍:Google Guava、Google Guice、Joda-Time
  19. C 标准库 - string.h之strncpy使用
  20. Swift &amp; Unicode

热门文章

  1. windows线程函数必须为全局函数或者静态函数(转)
  2. rest framework之路由组件
  3. CSIC_716_20191217【事务、视图、触发器、存储过程、索引】
  4. 影响Acorn for Mac图像打印质量的因素有什么?怎样处理这些因素才能得到打印效果最佳的图像?
  5. 【leetcode】958. Check Completeness of a Binary Tree
  6. Delphi ADOQuery的 DisableControls 和 EnableControls方法
  7. security安全框架 配置
  8. 学习android文档 -- Adding the Action Bar
  9. C++之string面试问题
  10. springboot使用自带连接池连接postgre