#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
struct node
{
ll x,h;
} Tr[];
int n,tr1[],tr2[];
bool cmp(node s1,node s2)
{
return s1.x<s2.x;
}
bool cmp1(node s1,node s2)
{
return s1.h<s2.h;
}
int lowbit(int x)
{
return x&(-x);
}
void insert(int x,int c,int *s) //s为对应的传递过来的数组
{
for(int i=x;i<=n;i+=lowbit(i))
s[i]+=c;
}
int sum(int x,int *s)
{
int ans=;
for(int i=x;i;i-=lowbit(i))
ans+=s[i];
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=; i<=n; i++)
scanf("%lld %lld",&Tr[i].x,&Tr[i].h);
//按照从小到大的把x顺序排序
sort(Tr+,Tr+n+,cmp);
//离散化坐标
int ji=Tr[].x;
Tr[].x=;
for(int i=; i<=n; i++)
{
//如果等于前一个,那么排名也一样
if(Tr[i].x==ji)
Tr[i].x=Tr[i-].x;
//不相等,说明小于,那么就赋离散化之后的值
else
{
ji=Tr[i].x;
Tr[i].x=i;
}
}
//记录最大的数下边用
int jilu=Tr[n].x;
//按照高度从小到大进行排序
sort(Tr+,Tr+n+,cmp1);
//离散化高度
ji=Tr[].h;
Tr[].h=;
for(int i=; i<=n; i++)
{
if(Tr[i].h==ji)
Tr[i].h=Tr[i-].h;
else
{
ji=Tr[i].h;
Tr[i].h=i;
}
}
ll ans=;
//第三次进行排序
//按高度排序
sort(Tr+,Tr+n+,cmp1);
memset(tr1,,sizeof tr1);
memset(tr2,,sizeof tr2);
for(int i=; i<=n; i++)
{
//记录所有比这个数小的和
insert(Tr[i].x,Tr[i].x,tr1);
//记录所有比这个数小的个数 每个点上记为1
insert(Tr[i].x,,tr2);
}
//xiao表示比对应坐标小
int xiao;
//da表示比对应坐标大
int da;
for(int i=; i<n; i++)
{
//找出比这个数小的个数*这个数-比这个数小的所有数之和
//相当于:当前这个数分别减去比他小的
xiao=sum(Tr[i].x-,tr2)*Tr[i].x-sum(Tr[i].x-,tr1);
//找出比这个数大的数的和-这个数*比这个数大的个数
da=(sum(jilu,tr1)-sum(Tr[i].x,tr1))-(sum(jilu,tr2)-sum(Tr[i].x,tr2))*Tr[i].x;
//高度取小 此时是按高度排序的
//坐标取差
ans+=(xiao+da)*Tr[i].h;
//把这个用过的数从删除
insert(Tr[i].x,-Tr[i].x,tr1);
//把这个数位置上减去1
insert(Tr[i].x,-,tr2);
}
printf("%lld\n",ans);
}
return ;
}

最新文章

  1. Linux Buffers和Cached的区别(转)
  2. maven--composer---setting.xml(updatepolicy)---mvn install , mvn deploy
  3. MySql 日期函数
  4. x-debug配置简述 - chunyu
  5. Struts2文件下载
  6. 用paint 计算字符串的像素宽度
  7. OD: ASLR
  8. EF 5.0 帮助类 增删改查
  9. CentOs 系统启动流程相关
  10. [LeetCode] Longest Word in Dictionary 字典中的最长单词
  11. RxJava操作符(02-创建操作)
  12. 使用handler倒计时
  13. luogu[愚人节题目3]现代妖怪殖民地 NTT
  14. nodeJs 资料
  15. cloud配置中心遇到的坑
  16. luogu1540 [NOIp2011]机器翻译 (队列)
  17. 构造函数constructor 与析构函数destructor(四)
  18. 奇技淫巧之 unordered_map
  19. Java 单生产者消费者问题
  20. ny16 矩形嵌套

热门文章

  1. Python Namespace - 命名空间
  2. VMware复制Linux虚拟机后网络配置
  3. 安装Debian的磨磨唧唧
  4. HDU 2018 DP
  5. ResNet详解与分析
  6. 响应式Web设计:构建令人赞叹的Web应用程序的秘诀
  7. Windows下配置开机自启Tomcat服务
  8. java的异常体系 及强制转换
  9. Linux学习小记(2)---installation
  10. 手把手教你搭建 ELK 实时日志分析平台