poj2352_II和III

灰太狼 2021-12-08 19:53 204阅读 0赞

这个题的第二个版本：

同2299\_II,也是压缩到1--n范围内，找出已知序列的相对顺序，然后构建树状数组。这里也需要一个辅助的数组。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <stdio.h>
     3 #include <memory.h>
     4 #include <algorithm>
     5 using namespace std;
     6 //516k 188ms
     7 const int maxnum=15001;
     8 struct node
     9 {
    10     int digit;
    11     int number;
    12 }array[maxnum],t[maxnum]; //t辅助数组
    13 int tree[maxnum];
    14 int res[maxnum];
    15 int n;
    16 
    17 void update(int index,int add)
    18 {
    19     while(index<=n)
    20     {
    21         tree[index]+=add;
    22         index+=(-index)&index;
    23     }
    24 }
    25 
    26 int getsum(int index)  //原序列中index位置之前小于等于array[index]的个数
    27 {
    28     int sum=0;
    29     while(index>0)
    30     {
    31         sum+=tree[index];
    32         index-=(-index)&index;
    33     }
    34     return sum;
    35 }
    36 
    37 bool cmp(struct node a,struct node b)
    38 {
    39     if(a.digit==b.digit)  //因为我离散化了，然后坐标里有重复的数字，因此需要在这里保存稳定性
    40         return a.number<b.number;
    41     return a.digit<b.digit;
    42 }
    43 
    44 
    45 int main()
    46 {
    47     scanf("%d",&n);
    48     int i,temp;
    49     for(i=1;i<=n;i++)
    50     {
    51         scanf("%d%d",&array[i].digit,&temp);
    52         t[i].digit=array[i].digit;
    53         t[i].number=i;
    54     }
    55     sort(t+1,t+1+n,cmp);
    56 
    57     for(i=1;i<=n;i++)
    58         array[t[i].number].number=i; //得到相对位置
    59     memset(tree,0,sizeof(tree));
    60     memset(res,0,sizeof(res));
    61     for(i=1;i<=n;i++)
    62     {
    63         update(array[i].number,1);
    64         res[getsum(array[i].number)-1]++; //这里要减一，不包括它本身
    65     }
    66     for(i=0;i<n;i++)
    67         printf("%d\n",res[i]);
    68     return 0;
    69 }
    70 
    71 /*
    72 5
    73 1 1
    74 5 1
    75 7 1
    76 3 3
    77 5 5
    78 */

第三个版本不需要压缩，直接离散到大于等于1的范围内即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <stdio.h>
     3 #include <memory.h>
     4 #include <algorithm>
     5 using namespace std;
     6 //408k 125ms
     7 const int maxnum=15001;
     8 const int maxdigit=32005;
     9 int array[maxnum]; //t辅助数组
    10 int tree[maxdigit];
    11 int res[maxnum];
    12 int n;
    13 
    14 void update(int index,int add)
    15 {
    16     while(index<maxdigit)
    17     {
    18         tree[index]+=add;
    19         index+=(-index)&index;
    20     }
    21 }
    22 
    23 int getsum(int index)  //原序列中index位置之前小于等于array[index]的个数
    24 {
    25     int sum=0;
    26     while(index>0)
    27     {
    28         sum+=tree[index];
    29         index-=(-index)&index;
    30     }
    31     return sum;
    32 }
    33 
    34 int main()
    35 {
    36     scanf("%d",&n);
    37     int i,temp;
    38     for(i=1;i<=n;i++)
    39         scanf("%d%d",&array[i],&temp);
    40 
    41     memset(tree,0,sizeof(tree));
    42     memset(res,0,sizeof(res));
    43     for(i=1;i<=n;i++)
    44     {
    45         update(array[i]+1,1);
    46         res[getsum(array[i]+1)-1]++; //这里要减一，不包括它本身
    47     }
    48     for(i=0;i<n;i++)
    49         printf("%d\n",res[i]);
    50     return 0;
    51 }
    52 
    53 /*
    54 5
    55 1 1
    56 5 1
    57 7 1
    58 3 3
    59 5 5
    60 */

转载于:https://www.cnblogs.com/pushing-my-way/archive/2012/08/19/2646214.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/1925663ab3424f858aceaa20d6a3d1b9.png