給定1~n的一個排列 用A[]數組保存,問有多少下標(a,b,c,d)四元組滿足:
a
題目中n的范圍是50000,O(n^2) 復雜度肯定超時。那麼這題明顯考察的是log2(n)的算法,對於這題可以用線段樹或者樹狀數組,同時要用到輸入外掛,不然會超時。
枚舉c的位置,那麼每一次枚舉中的方法數為 1~c-1 中(a,b)的個數 乘以 c~n中(c,d)的個數。累加起來即為答案。
1~c-1中(a,b)的個數相當於枚舉b的位置,然後計算出b前面有多少數比A[b]小,該值要保存下來,下一次枚舉c的時候,該值再加上c-1前面有多少比a[c-1]小的數即為當前情況下1~c-1中(a,b)的個數,也就是b=c-1的時候,因為枚舉b之前的情況已經算過了。
因為當算c時只是算出 比c小的方法數,這個只是滿足比c小的二元組的個數。而c前面的二元組也要計算在內,所以要加上c前面的比c小的個數。
用樹狀數組來做。本題n范圍50000,而且每個數都不相同很關鍵。所以我們就開辟n個位置,一開始每個位置都是0,其實每個位置不是0就是1,因為每個數只有一個。
比如 1 3 2 4 5
一開始 c數組 0 0 0 0 0
先統計,再輸入,因為計算a[i]前面有多少比它小的數,不包括它自己,而樹狀數組計算和的時候,要包括它自己。
i=1,樹狀數組求和前綴和 pre[1]=0 ,
此時0 0 0 0 0, 輸入1,變為 1 0 0 0 0
i=2,a[2]=3,要看 3前面有多少個數,也就是看c數組的3個位置前面有多少個1,1代表已經輸入,
發現1 0 0 0 0前三個數只有一個1,也就是pre[2]=1 (輸入的第二個數之前只有1個比它小的),輸入3以後,c數組變為 1 0 1 0 0
i=3, a[3]= 2, 要看2前面有多少個數,也就是看c數組前2個位置前面有多少個1,發現10100前兩個數中只有一個1,也就是pre[3]=1前綴和可以算出來,那麼後綴和 = num2[i] = n-i-a[i]+num[i]+1;
AC代碼
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 10;
int n;
ll C[N], a[N];
inline void read(ll &x) {
int flag = 0;
x = 0;
char c = getchar();
if(c == '-')
flag = 1;
while(c < '0' || c > '9') {
if(c == '-')
flag = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
if(flag) x = -x;
}
inline int lowbit(int x) {
return x & (-x);
}
int query(int x) {
int ret = 0;
while(x > 0) {
ret += C[x];
x -= lowbit(x);
}
return ret;
}
void add(int x, int d) {
while(x <= n) {
C[x] += d;
x += lowbit(x);
}
}
int num[N] , num2[N];
int main() {
int T;
scanf("%d", &T);
while(T--) {
ll ans = 0, pre = 0;
scanf("%d", &n);
memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++) {
read(a[i]);
num[i] = query(a[i]); //計算a[i]之前比a[i]小的數字
num2[i] = n-i-a[i]+num[i]+1; //計算a[i]之後比a[i]大的數字
add(a[i], 1);
ans += pre * num2[i];
pre += num[i];
}
printf("%lld\n", ans);
}
return 0;
}