当前位置：首页 > news >正文

详解Pku2352 数星星Stars以及star加强版

news 来源：原创 2024/9/20 12:03:13

前言

在看之前建议先看一下

【学习笔记】详解树状数组-CSDN博客

一.数星星Stars

思路

可以不管其y坐标，只看x坐标，构成数列(1,5,7,3,5),坐标数列最开始为空

当加入1时，在它左边没有数字于等于它，所以输出0，然后在1这个位置加上1

当加入5时，在它左边有1个数字小于等于它，所以输出1 ，然后在5这个位置加上1

当加入7时，在它左边有2个数字小于等于它，所以输出2 ，然后在7这个位置加上1

当加入3时，在它左边有1个数字小于等于它，所以输出1 ，然后在3这个位置加上1

当加入5时，在它左边有3个数字小于等于它，所以输出3 ，然后在5这个位置加上1

我们可以利用树状数组进行统计计数。
以坐标的值代表数字的大小，坐标上打标志的次数代表某个数字是否出现过。

注意星座下标可能为0，但树状数组中下标不能为0，所以要所有星座整体右移一位。

注意：
1:是在某个坐标上加入某个数字
2:星星的个数与星星的坐标是两个概念
本题中星星会有60000个，但坐标值只有32000

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000001],op,t,tt,c[1000001],maxn,ans[1000001],x[1000001],y;
int lowbit(int x)
{return (x & (-x));
}
void add(int p,int num)
{while(p <= maxn){c[p] += num;p += lowbit(p);}
}
int query(int p)
{int tmp = 0;while(p)   {   tmp += c[p];      p -= lowbit(p);   }   return tmp;
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){cin>>x[i]>>y;x[i]++;maxn = max(x[i],maxn);}for(int i = 1;i <= n;i++) add(x[i],1),cout<<query(x[i]) - 1<<endl;return 0;
}

二.star加强版

思路

如果星星的坐标值非常大，怎么办？
解决方案：离散化进行处理

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000001],g[1000001],op,t,tt,c[1000001],maxn,ans[1000001],x[1000001],y;
int lowbit(int x)
{return (x & (-x));
}
void add(int p,int num)
{while(p <= maxn){c[p] += num;p += lowbit(p);}
}
int query(int p)
{int tmp = 0;while(p)   {   tmp += c[p];      p -= lowbit(p);   }   return tmp;
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){cin>>g[i];x[i] = g[i];}sort(g + 1,g + 1 + n);int nt = unique(g + 1,g + n + 1) - g - 1;for(int i = 1;i <= n;i++) x[i] = lower_bound(g + 1,g + nt + 1,x[i]) - g;for(int i = 1;i <= n;i++) maxn = max(x[i],maxn);for(int i = 1;i <= n;i++) add(x[i],1),cout<<query(x[i]) - 1<<' ';return 0;
}