HDU - 1541 Stars 【树状数组】
2024-08-29 14:27:54
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1541
题意
求每个等级的星星有多少个
当前这个星星的左下角 有多少个 星星 它的等级就是多少
和它同一水平线的左边的星星 以及 同一竖直线的下边的星星也算在内
思路
因为题目给出的x y 坐标 是按照 以 y 为第一关键词 x 为第二关键词 排序后给出的
那么 对于当前的星星来说,在它之前给出的星星中,都是在它下边的
所以 我们就可以不用管 Y 坐标 只用X 坐标
形成一个序列 就是求这个序列的 所有逆序对的个数
树状数组
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a) memset(a, 0, sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
const double PI = acos(-1.0);
const double E = exp(1.0);
const double eps = 1e-30;
const int INF = 0x3f3f3f3f;
const int maxn = 32000 + 5;
const int MOD = 1e9 + 7;
int a[maxn];
int sum[maxn];
int lowbit(int x)
{
return x & (-x);
}
int Sum(int n)
{
int ans = 0;
while (n > 0)
{
ans += a[n];
n -= lowbit(n);
}
return ans;
}
void add(int x)
{
while (x <= maxn)
{
a[x]++;
x += lowbit(x);
}
}
int main()
{
int n;
while (~scanf("%d", &n))
{
CLR(sum);
CLR(a);
int x, y;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
sum[Sum(++x)]++;
add(x);
}
for (int i = 0; i < n; i++)
printf("%d\n", sum[i]);
}
}
最新文章
- 关于 m4 文本处理引擎
- 开发中常用js记录(二)
- 7.9 数据注解特性--ForeignKey
- openstack网络(neutron)模式之GRE的基本原理
- Python起步(2)
- ANDROID_MARS学习笔记_S01原始版_013_广播机制二
- JavaScript判断数据类型总结
- 【HDOJ】2144 Evolution
- CentOS6.5编译安装Redis
- SQL数据库的多表查询
- 04_Javascript初步第三天
- Centos搭建mysql/Hadoop/Hive/Hbase/Sqoop/Pig
- 26.app后端怎么架设推送服务
- vs2013修改书签(vs书签文件位置)
- es分页搜索
- Ubuntu 安装 VS code
- 201621123008 《Java程序设计》第14周学习总结
- yaml格式
- ehcache配置:使用Spring+SpringMVC+Mybatis或者有shiro
- The pit of an if statement in Java
热门文章
- RMQ(区间求最值)
- Andfix热修复框架原理及源代码解析-上篇
- mongodb配置副本集(多台服务器间的副本集搭建) replica[ˈrɛplɪkə]
- js:我们应该如何去了解JavaScript引擎的工作原理(转)
- 设计模式之MVC设计模式初阶
- Javascript模式(一) 单例模式
- PCA的数学原理Matlab演示
- Anaconda2
- 现在有一张半径为r的圆桌,其中心位于(x,y),现在他想把圆桌的中心移到(x1,y1)。每次移动一步,都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。
- ip获取位置