j247 - 111北二6a.不平衡配對數

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定一個數列 a 和一個整數 k，有多少個配對 (a[i], a[j]) 滿足 a[i] * k + 1 <= a[j]。

解題思路

這題可以使用 Binary Indexed Tree (BIT) 來有效地計算滿足條件的配對數。BIT 是一種資料結構，可以用來快速計算前綴和，並支援單點更新。

解題的思路是，對於數列中的每個元素 a[i]，我們需要計算有多少個後面的元素 a[j] 滿足 a[i] * k + 1 <= a[j]。我們可以利用 BIT 來記錄已經出現過的元素，然後查詢 BIT 中大於等於 a[i] * k + 1 的元素的數量。

具體步驟如下：

1. 初始化 BIT。
2. 遍歷數列 a。
3. 對於每個元素 a[i]，計算 a[i] * k + 1。
4. 查詢 BIT 中大於等於 a[i] * k + 1 的元素的數量，並將其加到答案中。
5. 將 a[i] 加入 BIT。

複雜度分析

• 時間複雜度: O(n log m)，其中 n 是數列的長度，m 是數列中最大元素的範圍 (在本題中 m = 1000)。
• 空間複雜度: O(m)，用於儲存 BIT。

程式碼

#include <iostream>
using namespace std;
int n,k,ans,a,bit[1005];
int lw(int x){
	return x&-x;
}
void up(int x){
	for(int i=x;i>0;i-=lw(i))
		++bit[i];
}
int sum(int x){
	int rt=0;
	for(int i=x;i<=1000;i+=lw(i))
		rt+=bit[i];
	return rt;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> k;
	for(int i=0;i<n;++i){
		cin >> a;
		ans+=sum(1000)-sum(a*k);
		up(a);
	}
	cout << ans;
}