Disharmony Trees HDU - 3015 树状数组+离散化
2024-10-08 08:19:01
#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 ;
}
最新文章
- Linux Buffers和Cached的区别(转)
- maven--composer---setting.xml(updatepolicy)---mvn install , mvn deploy
- MySql 日期函数
- x-debug配置简述 - chunyu
- Struts2文件下载
- 用paint 计算字符串的像素宽度
- OD: ASLR
- EF 5.0 帮助类 增删改查
- CentOs 系统启动流程相关
- [LeetCode] Longest Word in Dictionary 字典中的最长单词
- RxJava操作符(02-创建操作)
- 使用handler倒计时
- luogu[愚人节题目3]现代妖怪殖民地 NTT
- nodeJs 资料
- cloud配置中心遇到的坑
- luogu1540 [NOIp2011]机器翻译 (队列)
- 构造函数constructor 与析构函数destructor(四)
- 奇技淫巧之 unordered_map
- Java 单生产者消费者问题
- ny16 矩形嵌套