hlgHCPC2014校赛训练赛 1 BB.序列问题

题目：
计算序列 a[] 中，当 i < j < k, a[i] < a[j]&&a[j] > a[k], （a[i]和a[k]无需比较大小）这样的子序列个数。

Input
多组输入数据：

每组数据第一行一个数n：代表序列长度为n（0<n<50000）；

接下来第二行有n个数：代表序列元素的值a[i](0<a[i]<50000,且任意2个元素的值不相同)。

Output

对于每组数据输出符合条件的子序列的个数，每个输出占一行。

Sample Input
5
1 3 5 2 4
Sample Output
5

这个题目是小白书上乒乓比赛的变形（变简单了。。额……）

题目有一步优化，先对数值排序（这样的话如果n比较小的话，每次的求sum与add会比较省时间）

代码一：
这个代码应该会过：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int lowbit(int x)
 8 {
 9     return x&(-x);
10 }
11 
12 int n;
13 const int maxn=50005;
14 int c[maxn];
15 
16 void add(int i,int num)
17 {
18     while(i<=n)
19     {
20         c[i]+=num;
21         i+=lowbit(i);
22     }
23 }
24 
25 int getsum(int i)
26 {
27     int sum=0;
28     while(i>0)
29     {
30         sum+=c[i];
31         i-=lowbit(i);
32     }
33     return sum;
34 }
35 
36 struct point
37 {
38     int num;
39     int id;
40 }poin[maxn];
41 
42 
43 bool cmp(point p1,point p2)
44 {
45     return p1.num<p2.num;
46 }
47 
48 int summ[maxn];
49 
50 int main()
51 {
52     freopen("aa.txt","r",stdin);
53     while(scanf("%d",&n)!=EOF)
54     {
55         memset(c,0,sizeof(c));
56         for(int i=0;i<n;i++)
57         {
58             scanf("%d",&poin[i].num);
59             poin[i].id=i+1;
60         }
61         sort(poin,poin+n,cmp);
62         long long  int ans=0;
63         for(int i=0;i<n;i++)
64         {
65             ans+=getsum(poin[i].id)*(getsum(n)-getsum(poin[i].id));
66             add(poin[i].id,1);
67         }
68         printf("%lld
",ans);
69     }
70     return 0;
71 }

View Code

底下的代码留着oj加题的时候测试一下：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int lowbit(int x)
 8 {
 9     return x&(-x);
10 }
11 
12 const int maxn=50005;
13 int c[maxn];
14 
15 void add(int i,int num)
16 {
17     while(i<=50000)
18     {
19         c[i]+=num;
20         i+=lowbit(i);
21     }
22 }
23 
24 int getsum(int i)
25 {
26     int sum=0;
27     while(i>0)
28     {
29         sum+=c[i];
30         i-=lowbit(i);
31     }
32     return sum;
33 }
34 int a[maxn];
35 
36 int summ[maxn];
37 
38 int main()
39 {
40     int n;
41     freopen("aa.txt","r",stdin);
42     while(scanf("%d",&n)!=EOF)
43     {
44         memset(c,0,sizeof(c));
45         long long int ans=0;
46         for(int i=1;i<=n;i++)
47         {
48             scanf("%d",&a[i]);
49             ans+=getsum(a[i])*(getsum(50000)-getsum(a[i]));
50             add(a[i],1);
51         }printf("%lld
",ans);
52     }
53     return 0;
54 }

View Code