Tokitsukaze and Strange Rectangle CodeForces - 1191F (树状数组,计数)
2024-09-05 03:25:39
大意: 给定$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);
}
最新文章
- spring框架学习(三)
- iOS新手引导页的实现,源码。
- 学习Shell脚本编程(目录)
- Undefined symbols for architectureIOS
- 【leetcode❤python】 257. Binary Tree Paths
- 剑指offer系列19--栈的压入、弹出序列
- php运行步骤解析
- accept: Invalid argument linux 网络编程
- CSS的三种手段让元素脱离标准本文档流——浮动、绝对定位、固定定位
- 关于拒绝测试驱动开发(NoTDD)
- 安装java8
- Centos查看系统CPU个数、核心数、线程数
- eclipse使用技巧心得分享
- tyvj/joyoi 1305 最大子序和
- python修饰器(装饰器)以及wraps
- Go语言实践_实现一(服务器端)对多(客户端)在线聊天室
- Kotlin新语言简介和快速入门知识点
- 启用Win8/10(中文版/核心版/家庭版)中被阉割的远程桌面服务端
- 【Android】17.2 Activity与Local Service的绑定
- 图形管线之旅 Part2
热门文章
- ES索引文件和数据文件大小对比——splunk索引文件大小远小于ES,数据文件的压缩比也较ES更低,有趣的现象:ES数据文件zip压缩后大小和splunk的数据文件相当!词典文件tim/tip+倒排doc/pos和cfs文件是索引的大头
- Go by Example-变量
- cv相关博客文章
- 阿里巴巴微服务与配置中心技术实践之道 原创: 坤宇 InfoQ 2018-02-08
- SEQ!org.apache.hadoop.io.LongWritable
- 【边缘计算】 Edge Computing: Vision and Challenges
- Quartz.Net 学习随手记之03 配置文件
- Windows 7下安装MySQL Server卡在Apply Security Settings的解决方案(转)
- render()中添加js函数
- iOS笔试题01