树状数组 HDOJ 1541 Stars
刚开始一点都不觉得是树状数组。。。有很长一段时间觉的排个序就行了。。。直到重新读题发现输入是按顺序的。。。不过值得注意的是输入的x,y可能是0,但是在树状数组中是不能为0的。。。最后加上一个十分酷炫(丧心病狂)的输入优化,直接跑第一面了。。
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#define maxn 32005
#define eps 1e-7
#define mod 1000000007
#define INF 99999999
#define lowbit(x) (x&(-x))
typedef long long LL;
using namespace std;
int tree[maxn];
int hash[maxn];
int n;
void add(int x)
{
for(int i=x;i<maxn;i =lowbit(i)) tree[i] =1;
}
int sum(int x)
{
int i, ans=0;
for(i=x;i>0;i-=lowbit(i)) ans =tree[i];
return ans;
}
int get(void)
{
int tmp=0;
char ch=getchar();
while(ch!=' ' && ch!='\n')
tmp=tmp*10 ch-'0', ch=getchar();
return tmp;
}
int main(void)
{
int i, x, y;
while(scanf("%d",&n)!=EOF){
getchar();
memset(tree, 0, sizeof tree);
memset(hash, 0, sizeof hash);
for(i=0;i<n;i ){
//scanf("%d%d",&x,&y);
x=get();
y=get();
x , y ;
hash[sum(x)] ;
add(x);
}
for(i=0;i<n;i ) printf("%d\n", hash[i]);
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhichihi
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
excel打印预览压线压字怎么办
PHP中文网 06-22