神犇救命!!!

#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 条评论

  • @ 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;
    }
    ```

    • @ 2016-08-11 10:07:58

      你的程序是O(n^2)的
      而树状数组是O(nlogn)的

  • 1

信息

ID
1066
难度
4
分类
数据结构 | 树状数组数据结构 | 线段树 点击显示
标签
(无)
递交数
4662
已通过
2017
通过率
43%
被复制
9
上传者