Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。
思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。
我们枚举j，通过求两次逆序对求出对于每个a[j]，满足a[i]>a[j]的i的个数，以及满足a[j]>a[k]的个数。
两个个数的乘积就是j作为中间数满足的三元组的个数，这样把所有的j累加就是答案。
其他的就是，要离散化，以及最后答案可能会爆long long?
1A，好爽啊哈哈哈。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 05 Sep 2016 03:40:20 PM CST
4File Name :code/cf/problem/61E.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E6+7;
32int a[N];
33int A[N];
34int H[N];
35int n;
36int m;
37int tree1[N<<2],tree2[N<<2];
38pair<LL,LL>ans[N];
39void PushUp(int rt,int *tree)
40{
41 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
42}
43void update(int p,int l,int r,int rt,int *tree)
44{
45 if (l==r)
46 {
47 tree[rt]++;
48 return;
49 }
50 int m = (l+r)>>1;
51 if (p<=m) update(p,lson,tree);
52 else update(p,rson,tree);
53 PushUp(rt,tree);
54}
55int query(int L,int R,int l,int r,int rt,int *tree)
56{
57// cout<<"L:"<<L<<" R:"<<R<<" l:"<<l<<" r:"<<r<<" rt:"<<rt<<endl;
58 if (L>R) return 0;
59 if (L<=l&&r<=R) return tree[rt];
60 int m = (l+r)>>1;
61 int ret = 0 ;
62 if (L<=m)
63 {
64 int res = query(L,R,lson,tree);
65 ret+=res;
66 }
67 if (R>=m+1)
68 {
69 int res = query(L,R,rson,tree);
70 ret +=res;
71 }
72 return ret;
73}
74int Hash( int x)
75{
76 return lower_bound(H,H+m,x)-H;
77}
78int main()
79{
80 #ifndef ONLINE_JUDGE
81 freopen("code/in.txt","r",stdin);
82 #endif
83 cin>>n;
84 m = n;
85 for ( int i = 0 ; i < n ; i++)
86 {
87 scanf("%d",&a[i]);
88 H[i] = a[i];
89 }
90 sort(H,H+m);
91 m = unique(H,H+m)-H;
92 int mx = 0 ;
93 for ( int i = 0 ; i < n ; i++) A[i] = Hash(a[i])+1,mx = max(mx,A[i]);
94 ms(tree1,0);
95 ms(tree2,0);
96 for ( int i = n-1 ; i >=0 ; i--)
97 {
98 LL tmp = LL(query(1,A[i]-1,1,mx,1,tree1));
99 ans[i].fst = tmp;
100 update(A[i],1,mx,1,tree1);
101 }
102 for ( int i = 0 ; i < n ; i++)
103 {
104 LL tmp = LL(query(A[i]+1,mx,1,mx,1,tree2));
105 ans[i].sec = tmp;
106 update(A[i],1,mx,1,tree2);
107 }
108 LL res = 0LL;
109 for ( int i = 0 ; i < n ; i++) res = res + ans[i].fst*ans[i].sec;
110 cout<<res<<endl;
111 #ifndef ONLINE_JUDGE
112 fclose(stdin);
113 #endif
114 return 0;
115}