简单的数列

P2398 - 简单的数列

Description

一个简单的数列问题：
给定一个长度为n的数列，求这样的三个元素 ai,aj,ak 的个数，满足 ai＜aj>ak，且 i＜j＜k 。

Input

第1行是一个整数n（1<=n<=50000）。
接下来n行，每行一个元素ai（0<=ai<=32767）。

Output

一个数，满足 ai＜aj>ak (i＜j＜k) 的个数。

Sample Input

1

Sample Output

6

Hint

数据范围：
对于30%的输入数据有n<=200。
对于80%的输入数据有n<=10000。
对于100%的输入数据有n<=50000。



先从左往右扫一遍，每扫到一个数字，把它的值在线段树中＋１。每个点查询线段树中０到a[i]-1，记录为l[i]。

再从右往左做相同的处理，记为r[i]，记得线段树清空。

最后答案就是Σl[i]*r[i]。

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 50010
15 #define RG register
16 #define mi int mid=(l+r)>>1
17 #define ls o*2
18 #define rs o*2+1
19 #define LL long long
20 using namespace std;
21 int a[maxn],s1[maxn],s2[maxn],b[32767*4];
22 void add(int o,int l,int r,int p){
23   if(l==r){b[o]++;return;}
24   mi;
25   if(p<=mid) add(ls,l,mid,p);
26   else add(rs,mid+1,r,p);
27   b[o]=b[ls]+b[rs];
28 }
29 int find(int o,int l,int r,int u,int v)
30 {
31   if(v<u) return 0;
32   if(l>=u && r<=v) return b[o];
33   if(l>v || r<u) return 0;
34   mi;
35   if(v<=mid) return find(ls,l,mid,u,v);
36   else if(u>mid) return find(rs,mid+1,r,u,v);
37   else return find(ls,l,mid,u,mid)+find(rs,mid+1,r,mid+1,v);
38 }
39 int main()
40 {
41   freopen("queueb.in","r",stdin);
42   freopen("queueb.out","w",stdout);
43   int n,zdn=0;
44   scanf("%d",&n);
45   for(RG int i=1;i<=n;i++)
46     scanf("%d",&a[i]),zdn=zdn>a[i]?zdn:a[i];
47   for(RG int i=1;i<=n;i++){
48     s1[i]=find(1,0,zdn,0,a[i]-1);
49     add(1,0,zdn,a[i]);
50   }
51   memset(b,0,sizeof(b));
52   for(RG int i=n;i>=1;i--){
53     s2[i]=find(1,0,zdn,0,a[i]-1);
54     add(1,0,zdn,a[i]);
55   }
56   LL ans=0;
57   for(RG int i=1;i<=n;i++)
58     ans+=s1[i]*s2[i];
59   printf("%lld",ans);
60   return 0;
61 }