hdu1541 Stars(树状数组)_Code92007的博客-程序员秘密

技术标签：树状数组二维 # 线段树/树状数组思维题顺序对

题目

有n个点(xi,yi)

输入时保证按y升序，

即先按y小的输入，y相同时按x升序输入

如果对于(xi,yi)来说，

位于x<=yi&&y<=yi区域的点有ki个

则level[ki]++

最终输出level[0]到level[n-1]的值

思路来源

https://blog.csdn.net/ACMer_hades/article/details/46274927

题解

~~思路来源的题主忘了初始化C数组hhhh~~

其实乱序的话，按加粗题排序一下也能搞

然后既然是这样的输入，题目也给的那么明显

所以就相当于把二维降成一维的线性

这样就相当于统计在加入这个值之前有多少x值比它小

所以就变成了统计顺序对的裸题

BIT和线段树先统计区间和再插入一个点搞一搞就好了

心得

这题重点在于两处

①BIT是不能处理下标0的，

所以0<=x<=3W2要++x

②把二维降成一维统计之前的排序方法

struct node
{
	int x,y;
};
bool cmp(node a,node b)
{
	if(a.y!=b.y)return a.y<b.y;
	return a.x<b.x;
}

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;
const int maxn=32000;
int C[maxn+5],level[maxn+5]; 
int n,x,y;
int sum(int i)
{
	int ans=0;
	for(;i;i-=i&(-i))
	ans+=C[i];
	return ans;
}
void add(int i,int v)
{
	for(;i<=maxn+1;i+=i&(-i))
	C[i]+=v;
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(C,0,sizeof(C));
		memset(level,0,sizeof(level));
		for(int i=0;i<n;++i)
		{
			scanf("%d%d",&x,&y);
			x++;//将x搞到1-32001 BIT下标不能为0
			level[sum(x)]++;
			add(x,1); 
		}
		for(int i=0;i<n;++i)
		printf("%d\n",level[i]);
	}
	return 0;
}

本文链接：https://blog.csdn.net/code92007/article/details/87921719

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

XML到底是干什么的_misc.xml是干什么的_明昊昊同学的博客-程序员秘密

定义XML本身是一种格式规范，是一种包含了数据以及数据说明的文本格式规范。抛砖比如，我们要给对方传输一段数据，数据内容是“too young,too simple,sometimes naive”，要将这段话按照属性拆分为三个数据的话，就是，年龄too young，阅历too simple，结果sometimes naive。我们都知道程序不像人，可以体会字面意思，并自动拆分出数据，因此，...

数字图像处理课程作业1-大米检测_米粒图像预处理实验_ZHHHHHJ66的博客-程序员秘密

写在最前这是我大学课程的数字图像处理的实验报告，代码大部分是从网上直接复制使用，小部分是我自己改写的，可以直接运行。内容比较详细1.实验目的:综合利用滤波、分割、图像分割、特征描述等知识，实现大米实际尺度、整精米的检测2.实验要求：检测出图中的碎米，并在相应的米粒上打上标志。3.实验分析：①米粒与背景对比不明显，需要用一个阈值对其进行二值化②背景存在噪声需要对其进行去噪声③找到对应的米粒需要对其进行轮廓检测④找到其中的碎米需要对其进行面积阈值处理，找出面积小的碎米流程图如下

arcpy批量输出单个要素图片，排除相邻要素_鱼·肉·蛋的博客-程序员秘密

通过arcgis数据驱动页面可以输出要素类中每一个要素对应的图片，但是有部分需求如下：输出每一个要素图片，且图片上只能显示该要素，与其相邻或者相交的要素不可显示。通过arcpy代码实现如下：# coding=utf-8import arcpymxd = arcpy.mapping.MapDocument(r"F:\map.mxd")lyr = arcpy.mapping.ListL...

题解：最长回文子串（4种解法）_v-space的博客-程序员秘密

题目：最长回文子串难度：中等一、描述二、题解：2.1 暴力法（O(N^3)）解释：循环三次。第一次起始点循环；第二次终止点循环（从最右边开始到起始点为止）；第三次起始点开始终止点结束，当两个值不相等时候跳出循环。只有完整进行第三次循环才满足回文串的条件。class Solution: def longestPalindrome(self, s: str) -> str: max_ = 1 max_str = s[0] length

mall学习所需知识点_macrozheng的博客-程序员秘密

由于mall项目涉及到很多知识点，比如SpringBoot、ElasticSearch、Redis、Mongodb等，本教程不会详细讲述这些，只会讲述本项目相关部分，所以...

Openwrt Image Builder/SDK 初探_weixin_30470857的博客-程序员秘密

image builder和SDK既可以从官网上下载，又可以自己进行编译（make menuconfig）。官网上下载的是预先帮你编译好的，这样可以大量节省自己编译源码花的时间，这两个东西相当于半成品，最后的东西还是要你自己生成的。开发流程如下：在编译时将image builder和sdk这两项勾上之后，它们就可以被编译出来的。当然也可以从官网下载，不过官网编译出来...