【題解】Zerojudge f315 - 4. 低地距離

題目連結

題目大意

給定一個長度為 $2n$ 的陣列，其中 $1 \sim n$ 都剛好出現兩次。定義 $f(i)$ 為 $i$ 出現的兩個位置中間有幾個數字比他小。求 $\sum\limits_{i = 1}^n f(i)$。

• $1 \leq n \leq 10^5$

題解

我們先將每個數字出現的 index 儲存下來。假設 $pos_{i, j}$ 為數字 $i$ 第 $j$ 次 (0-based) 出現的 index，對於每個數字我們都想要知道 $pos_{i, 0} \sim pos_{i, 1}$ 中間有幾個數字比 $i$ 小。我們把出現過的數字設為 $1$，沒出現過的數字設為 $0$。由小到大檢查，查詢 $pos_{i, 0} \sim pos_{i, 1}$ 有幾個數字相當於區間求和。求出以後要記得把 $i$ 出現的位置 ($pos_{i, 0}$ 和 $pos_{i, 1}$) 設為 $1$。單點更新和區間求和的問題我們可以透過線段樹或是 BIT 等資料結構解決。以下的程式碼是用 BIT 實作。其他實作的細節請參考 code。

#include <bits/stdc++.h>

template<class S>
struct fenwick {
public:
	fenwick() : n(0) {}
	explicit fenwick(int _n) : n(_n), data(_n) {}

	void add(int p, S x) {
		for(int i = p + 1; i <= n; i += i & -i) {
			data[i - 1] += x;
		}
	}

	// [0, p)
	S get(int p) const {
		auto ans = S();
		for(int i = p; i > 0; i -= i & -i) {
			ans += data[i - 1];
		}
		return ans;
	}

	// [l, r)
	S sum(int l, int r) const { return get(r) - get(l); }

	// 0-based
	int kth(S k) const {
		int x = 0;
		for(int i = 1 << std::__lg(n); i > 0; i >>= 1) {
			if (x + i <= n && k >= data[x + i - 1]) {
				x += i;
				k -= data[x - 1];
			}
		}
		return x;
	}

private:
	int n;
	std::vector<S> data;
};

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<vector<int>> a(n);
	for(int i = 0; i < 2 * n; i++) {
		int x;
		cin >> x;
		x--;
		a[x].push_back(i);
	}
	long long ans = 0;
	fenwick<int> fenw(2 * n);
	for(int i = 0; i < n; i++) {
		ans += fenw.sum(a[i][0], a[i][1] + 1);
		fenw.add(a[i][0], +1);
		fenw.add(a[i][1], +1);
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f315 - 4. 低地距離