vijos 1066 弱弱的战壕 树状数组
2024-08-25 16:22:08
描述
永恒和mx正在玩一个即时战略游戏,名字嘛~~~~~~恕本人记性不好,忘了-_-b。
mx在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,射程可以达到无限(“mx不赢定了?!?”永恒ftING...@_@)。
但是,战壕有一个弱点,就是只能攻击它的左下方,说白了就是横纵坐标都不大于它的点(mx:“我的战壕为什么这么菜”ToT)。这样,永恒就可以从别的地方进攻摧毁战壕,从而消灭mx的部队。
战壕都有一个保护范围,同它的攻击范围一样,它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样,永恒就必须找到mx的战壕中保护对象最多的点,从而优先消灭它。
现在,由于永恒没有时间来计算,所以拜托你来完成这个任务:
给出这n个战壕的坐标xi、yi,要你求出保护对象个数为0,1,2……n-1的战壕的个数。
格式
输入格式
第一行,一个正整数n(1<=n<=15000)
接下来n行,每行两个数xi,yi,代表第i个点的坐标
(1<=xi,yi<=32000)
注意:可能包含多重战壕的情况(即有数个点在同一坐标)
输出格式
输出n行,分别代表保护对象为0,1,2……n-1的战壕的个数。
限制
各点2s(算是宽限吧^_^)
题意:给出一系列的点,求在某点坐下方有[1,n]个点的这样的点的个数。
思路:先就一维有序化,这样剩下一维只要使用前缀和的特性表示覆盖次数就可以惹。点坐标很小,都不用离散化
/** @Date : 2016-12-13-20.36
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/
#include<bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; int n;
struct yuu
{
int x, y;
}p[15010]; int t[35000];
int ans[35000];
int cmp(yuu a, yuu b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
} void add(int x)
{
while(x <= 32001)
{
t[x]++;
x += (-x) & x;
}
} int sum(int x)
{
int ans = 0;
while(x)
{
ans += t[x];
x -= (-x) & x;
}
return ans;
} int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
}
MMF(t);
MMF(ans);
sort(p, p + n, cmp);//先就一个维度有序化 for(int i = 0; i < n; i++)//再进行找个数
{
ans[sum(p[i].y)]++;
add(p[i].y);
}
for(int i = 0; i < n; i++)
printf("%d\n", ans[i]);
return 0;
}
最新文章
- Beta阶段第一次Scrum Meeting
- cloudera learning4:Hadoop集群规划
- runtime学习笔记
- Day9 summary
- Angular系列---- AngularJS入门教程03:AngularJS 模板(转载)
- 微软IOC容器Unity简单代码示例1
- VBA访问SQLSERVER2005筛选数据库
- Util
- ●BZOJ 1069 [SCOI2007]最大土地面积
- PAT1107:Social Clusters
- 【憩园】C#并发编程之异步编程(二)
- spring Environment
- .NET WebService 入门
- [Spark Streaming_1] Spark Streaming 概述
- Win10环境Tensorflow-GPU13.1/JupyterNotebook的安装
- php7 安装swoole4.0.4
- Centos7远程桌面 vnc/vnc-server的设置
- falsk注册etcd
- LeetCode——Palindromic Substrings
- Zookeeper--Watcher 和 ACL