- 弱弱的战壕
- 2016-08-07 20:19:22 @
#include<cstdio>
#include<algorithm>
using std :: sort;
int c[32010]={0},cnt[15010]={0},n;
int const B=32010;
struct tfz
{
int x,y;
}line[15010];
inline bool cmp(tfz a,tfz b) {
if (a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int lowbit(int z)
{
return z&-z;
}
int sum(int a)
{
int s=0;
for(;a>0;a-=lowbit(a))
s+=c[a];
return s;
}
void val(int a,int v)
{
for(;a<=B;a+=lowbit(a))
c[a]+=v;
}
int main()
{
scanf("%d",&n);
sort(line+1,line+n+1,cmp);
for(int i=1;i<=n;i++)
scanf("%d %d",&line[i].x,&line[i].y);
for(int i=1;i<=n;){
int p=0;
for(int j=i+1;line[j].x==line[i].x;j++)
p++;
int t=sum(line[i].x);
cnt[t+p]+=(p+1);
val(line[i].x,p+1);
i+=(p+1);
}
for(int i=0;i<n;i++)
printf("%d\n",cnt[i]);
return 0;
}
4 条评论
-
唐复之 LV 8 @ 2016-08-16 20:23:10
我刷题,刷树状数组的
-
2016-08-16 16:36:59@
那确实,树状数组时间复杂度小
-
2016-08-12 18:35:54@
修改了程序,只AC6个点:
```
#include<cstdio>
#include<algorithm>
using std :: sort;
int c[32010]={0},cnt[15010]={0},n;
int const B=15010;
struct tfz
{
int x,y;
}line[15010];
inline bool cmp(tfz a,tfz b) {
if (a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int lowbit(int z)
{
return z&-z;
}
int sum(int a)
{
int s=0;
for(;a>0;a-=lowbit(a))
s+=c[a];
return s;
}
void val(int a,int v)
{
for(;a<=B;a+=lowbit(a))
c[a]+=v;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++)
scanf("%d %d",&line[i].x,&line[i].y);
sort(line+1,line+n+1,cmp);
for(i=1;i<=n;){
int p=0;
for(j=i+1;line[j].x==line[i].x && line[j].y==line[i].y;j++)
p++;
int t=sum(line[i].x);
val(line[i].x,p+1);
cnt[(t+p)]+=(p+1);
i+=(p+1);
}
for(int i=0;i<n;i++)
printf("%d\n",cnt[i]);
return 0;
} -
2016-08-10 11:16:50@
这题为毛要用树状数组呢?
```c++
#include<cstdio>
#include<cstring>int ans1[15200], x[15200], y[15200], ans[15200], n;
int main()
{
memset(ans, 0, sizeof(ans));
memset(ans1, 0, sizeof(ans1));
scanf("%d", &n);for(int i = 1; i <= n; i++)
{
scanf("%d%d", &x[i], &y[i]);
}for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j && (x[i] >= x[j]) && y[i] >= y[j])
{
ans[i]++;
}for(int i = 1; i <= n; i++)
{
ans1[ans[i]]++;
}for(int i = 0; i < n; i++)
{
printf("%d\n", ans1[i]);
}return 0;
}
```
- 1