题目大意

在长为 $n$ 的序列 $A$，问有多少区间 $[l,r]$ 满足区间众数的出现次数严格大于 $\frac{r-l+1}{2}$。

分析

我发现我真的不会数据结构，只会推推式子啥的，这种要想的题根本想不来。

设区间 $[l,r]$ 中存在众数 $w$（显然满足题意必唯一），有

$$ \sum_{i=l}^r [a_i=w] > \frac{r-l+1}{2} $$

分离变量，可以得到

$$ 2\sum_{i=1}^l [a_i=w] - l < 2\sum_{i=1}^r [a_i=w] - r $$

考虑设置函数

$$ S_w(x) = 2\sum_{i=1}^x [a_i = w] - x = \sum_{i=1}^x [a_i = w] - \sum_{i=1}^x [a_i \ne w] $$

观察 $S_w(x)$ 的特性，即可发现其只由 $1, -1$ 组成，可以转化为二阶前缀和问题。

解释待补充。

template <class T>
struct fwtree_2 {
	fwtree<T> f1, f2, f3;
	vector<T> u;
	fwtree_2(int n = 0) : f1(n), f2(n), f3(n), u(n) {}
	template <class iter>
	void init(iter first, iter last) {
		copy(first, last, u.begin());
		T sum = u[0];
		for (int i = 1; i < u.size(); i++) {
			u[i] += u[i - 1] + sum;
			sum += u[i];
		}
	}
	void add(int l, int r, const T &t) {
		r++;
		f1.add(l, t), f1.add(r, -t);
		f2.add(l, t * l), f2.add(r, -t * r);
		f3.add(l, t * l * l), f3.add(r, -t * r * r);
	}
	T sum(int i) const {
		T ret = u[i] + f1.sum(i) * (i + 1) * (i + 2);
		ret += -f2.sum(i) * (2 * i + 3) + f3.sum(i);
		return ret / 2;
	}
	T sum(int l, int r) const {
		return sum(r) - sum(l - 1);
	}
};

using pii = pair<int, int>;

int main() {
	int n, type_;
	cin >> n >> type_;
	vector<vector<int>> B(n + 1);
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		B[a[i]].push_back(i);
	}

	ll ans = 0;
	const int off = n + 3;
	fwtree_2<ll> tr(n * 2 + 5);
	for (int i = 0; i < n; i++) {
		if (B[i].empty()) {
			continue;
		}
		B[i].push_back(n + 1);
		int last = 0, past_bi = 0;

		vector<pii> v;
		for (auto bi : B[i]) {
			int dif = bi - past_bi;
			int x = last - (dif - 1), y = last;
			ans += tr.sum(x - 1 + off, y - 1 + off);
			tr.add(x + off, y + off, 1);
			v.emplace_back(x + off, y + off);
			past_bi = bi, last -= dif - 2;
		}
		for (auto [x, y] : v) {
			tr.add(x, y, -1);
		}
	}
	cout << ans;
	return 0;
}

全部代码请看：Luogu/4x/P4062.cpp。