【Codeforces61E】Enemy is weak

Enemy is weak"/>

【Codeforces61E】Enemy is weak

翻译题面:求三元逆序组数目
E. Enemy is weak
time limit per test5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: “A lion is never afraid of a hundred sheep”.

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur’s opinion the weakness of an army is equal to the number of triplets i, j, k such that i < j < k and ai > aj > ak where ax is the power of man standing at position x. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.

Input
The first line of input contains a single number n (3 ≤ n ≤ 106) — the number of men in Roman army. Next line contains n different positive integers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — powers of men in the Roman army.

Output
A single integer number, the weakness of the Roman army.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Sample test(s)
input
3
3 2 1
output
1
input
3
2 3 1
output
0
input
4
10 8 3 1
output
4
input
4
1 5 4 3
output
1

跟二元逆序对一个样仍然排序,就是对一个树状数组外面再用另一个树状数组记录第一个树状数组的前缀和.时间复杂度 O(k⋅nlogn) $O(k\cdot n logn)$
我就是把 106 $10^6$看成了 105 $10^5$RE了你来咬我啊QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lowbit(x) (x&(-x))
#define MAXN 3000010
using namespace std;
void in(int &x)
{char ch=getchar();x=0;while (!(ch>='0'&&ch<='9')) ch=getchar();while ((ch>='0'&&ch<='9')) x=x*10+ch-'0',ch=getchar();
}
int n;
struct array
{long long c[MAXN];void add(int x,long long delta){while (x) c[x]+=delta,x-=lowbit(x);}long long sum(int x){long long ret=0;while (x<=n) ret+=c[x],x+=lowbit(x);return ret;}
}A,B;
struct num
{int id,data;bool operator <(const num& a)const{return data<a.data;}
}a[MAXN];
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) in(a[i].data),a[i].id=i;sort(a+1,a+n+1);long long ans=0;for (int i=1;i<=n;i++){ans+=B.sum(a[i].id);B.add(a[i].id,A.sum(a[i].id));A.add(a[i].id,1);}cout<<ans<<endl;
}