大意: 给定$n$个平面点, 定义集合$S(l,r,a)$表示横坐标$[l,r]$纵坐标$[a,\infty]$内的所有点. 求可以得到多少种不同的集合.

从上往下枚举底层最右侧点, 树状数组统计贡献.

#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int n, c[N], vis[N], b[N];
struct _ {
int x,y;
bool operator < (const _&rhs) const {
if (y!=rhs.y) return y>rhs.y;
return x<rhs.x;
}
} a[N];
int ID(int x) {
return lower_bound(b+1,b+1+*b,x)-b;
}
int qry(int x) {
int r = 0;
for (; x; x^=x&-x) r+=c[x];
return r;
}
int qry(int l, int r) {
return qry(ID(r))-qry(ID(l-1));
}
void add(int x) {
x = ID(x);
if (!vis[x]) {
vis[x] = 1;
for (; x<=*b; x+=x&-x) ++c[x];
}
}
int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d%d",&a[i].x,&a[i].y);
b[++*b]=a[i].x;
b[++*b]=a[i].x-1;
}
b[++*b]=0,b[++*b]=INF;
sort(b+1,b+1+*b),*b=unique(b+1,b+1+*b)-b-1;
sort(a+1,a+1+n);
ll ans = 0;
REP(i,1,n) {
int j=i;
while (j<n&&a[j+1].y==a[i].y) ++j;
REP(k,i,j) {
int L = qry(1,a[k].x-1);
int R = qry(a[k].x+1,k==j?INF:a[k+1].x-1);
ans += (ll)(L+1)*(R+1);
add(a[k].x);
}
i = j;
}
printf("%lld\n", ans);
}

最新文章

  1. spring框架学习(三)
  2. iOS新手引导页的实现,源码。
  3. 学习Shell脚本编程(目录)
  4. Undefined symbols for architectureIOS
  5. 【leetcode❤python】 257. Binary Tree Paths
  6. 剑指offer系列19--栈的压入、弹出序列
  7. php运行步骤解析
  8. accept: Invalid argument linux 网络编程
  9. CSS的三种手段让元素脱离标准本文档流——浮动、绝对定位、固定定位
  10. 关于拒绝测试驱动开发(NoTDD)
  11. 安装java8
  12. Centos查看系统CPU个数、核心数、线程数
  13. eclipse使用技巧心得分享
  14. tyvj/joyoi 1305 最大子序和
  15. python修饰器(装饰器)以及wraps
  16. Go语言实践_实现一(服务器端)对多(客户端)在线聊天室
  17. Kotlin新语言简介和快速入门知识点
  18. 启用Win8/10(中文版/核心版/家庭版)中被阉割的远程桌面服务端
  19. 【Android】17.2 Activity与Local Service的绑定
  20. 图形管线之旅 Part2

热门文章

  1. ES索引文件和数据文件大小对比——splunk索引文件大小远小于ES,数据文件的压缩比也较ES更低,有趣的现象:ES数据文件zip压缩后大小和splunk的数据文件相当!词典文件tim/tip+倒排doc/pos和cfs文件是索引的大头
  2. Go by Example-变量
  3. cv相关博客文章
  4. 阿里巴巴微服务与配置中心技术实践之道 原创: 坤宇 InfoQ 2018-02-08
  5. SEQ!org.apache.hadoop.io.LongWritable
  6. 【边缘计算】 Edge Computing: Vision and Challenges
  7. Quartz.Net 学习随手记之03 配置文件
  8. Windows 7下安装MySQL Server卡在Apply Security Settings的解决方案(转)
  9. render()中添加js函数
  10. iOS笔试题01