原題鏈接

提供一種復雜度多一個 \(\log\) 的做法。

解析

我最初的想法是將詢問離線下來，將球按權值排序，對于每個球 \(i\) 維護一個指針指向滿足 \(a_i \cdot a_j \ge p\) 的第一個 \(j\)，然后在處理詢問的時候去移這個指針。

但是我們甚至無法接受在處理每個詢問時遍歷所有指針的復雜度。想到這一點，我就直接否掉了這個做法，但是其實可以繼續做。

由于處理一個更大的 \(p\) 時并不一定是所有指針都需要移，所以考慮維護一個小根堆來存每個球當前指針指向的位置，按照對應值的乘積排序。但是這樣總的指針移動次數依然可以達到 \(O(n ^ 2)\)。

注意到對于權值相同的小球，指針指向的位置永遠相同。所以直接去重，這樣對于權值為 \(x\) 的小球，指針至多移動 \(\lceil\frac{p_{max}}{x}\rceil\) 次，根據調和級數的結論總移動次數就是 \(O(p \log n)\)。去重之后計算貢獻需要預處理一個每種小球出現次數的后綴和。

總時間復雜度 \(O(p\log^2 n)\)。

代碼

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 3e6 + 5,M = 3.2e4 + 5;
ll a[N],cnt[N],suf[N],ans[N];
vector<ll> num;
struct cmp{
	bool operator()(pii p1,pii p2){
		return num[p1.first] * num[p1.second] > num[p2.first] * num[p2.second];
	}
};
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		num.push_back(a[i]);
		cnt[a[i]]++;
	}
	for(int i=N - 2;i>=1;i--){
		suf[i] = suf[i + 1] + cnt[i];
	}
	int m;
	cin>>m;
	vector<pii> q;
	for(int i=1;i<=m;i++){
		int p;
		cin>>p;
		q.push_back({p,i});
	}
	sort(q.begin(),q.end());
	sort(num.begin(),num.end());
	num.erase(unique(num.begin(),num.end()),num.end());
	int l = num.size();
	priority_queue<pii,vector<pii>,cmp> pq;
	ll res = 1ll * n * (n - 1);//所有數對均合法的方案數
	for(int i=0;i<l;i++){
		pq.push({i,0});
	}
	for(int i=0;i<m;i++){
		int x = q[i].first;
		while(!pq.empty() && num[pq.top().first] * num[pq.top().second] < x){//注意判空
			pii tp = pq.top();
			pq.pop();
			res -= cnt[num[tp.first]] * (suf[num[tp.second]] - (tp.second <= tp.first));//注意在拿第二個球的時候第一個球不會放回去
			int npos = tp.second;
			while(npos < l && num[tp.first] * num[npos] < x){
				npos++;
			}
			if(npos < l){
				pq.push({tp.first,npos});
				res += cnt[num[tp.first]] * (suf[num[npos]] - (npos <= tp.first));
			}
		}
		ans[q[i].second] = res;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}