POJ2352【树状数组】
2024-10-15 05:21:24
个人NO。1
一开始题意理解有错。
一星星左下边有N颗星星,那它的等级就是N。
一开始理解必须X,Y两个坐标都小于,后来根据样例看了一下只要左下方即可,X,Y坐标都小于等于即可,但不包括星星本身。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int lowbit(int x)
{
return x&-x;
}
int c[32005];
int x[32005];
int n;
int ans[32005];
int visit[32005];
int a[32005];
void add(int x,int y)//后面的所有的值得更新,不包括自身
{
while(x<=32005)
{
c[x]+=y;
x+=lowbit(x);
}
}
int sum(int x)
{
int ret=0;
while(x>0)
{
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
memset(x,0,sizeof(x));
memset(ans,0,sizeof(ans));
int x,y;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&y);
if(visit[a[i]+1]==0)
{
add(a[i]+2,1);
visit[a[i]+1]=1;
}
else
add(a[i]+1,1);//c[i]表示比i坐标小的个数
ans[sum(a[i]+1)]++;
} for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
}
return 0;
}
题目有陷阱就是坐标可以输入0,这对lowbit不适应。
对树状数组的用法更了解了一下,大致用法如下:balabala....
最新文章
- JavaScript中尺寸、坐标
- HBase+Phoenix整合入门--集群搭建
- chrome远程调试真机上的app
- 【bzoj1499】 NOI2005—瑰丽华尔兹
- 功放AUX接口解析
- Java 比较两张图片的相似度
- 【转】二叉树 VS hashtable
- SqlServer快捷键整理
- JSP自定义标签——简单标签(2)
- PHP文本路径转换为链接文字
- 自定义ExtJS主题
- 轻松测试 logstash 的配置文件
- Eclipse如何新建TOMCAT并配置Server Locations和Publishing属性
- Bayesian RL and PGMRL
- CString int转换
- Liferay7 BPM门户开发之1:Liferay7开发环境准备
- 消息队列第一篇:MessageQueue介绍
- Expert C Programming 阅读笔记(CH2)
- 页面操作表单不会调用表单 value 属性的 set 函数
- 【题解】JSOI2009游戏