当前位置：首页 > ops >正文

CF2056 D. Unique Median(2200)

ops 2025/6/25 16:49:26

好题！

Problem - D - Codeforces

题意：

思路：

首先可以发现区间长度为奇数的区间一定满足，考虑求出不满足的偶数区间数量，最后总区间数量减去即可。

什么样的偶数区间是不满足的？对于不满足的偶数区间一定有这样一个性质：这个区间恰好有一半的数字满足小于等于某个数。我们可以枚举这个数，假设这个数为k, $c_i$ 表示前i个数中有ci个数小于等于k，对于非法区间[l,r]，应该满足

$\begin{aligned} c_r - c_{l-1} &= \frac{r - l + 1}{2}\\ \end{aligned}$

$\begin{aligned} 2c_r - r &= 2c_{l-1} - l + 1. \end{aligned}$

枚举右区间，将等式左边的值装进桶里，我们需要找到与等式左边相等的值然后减去其贡献。

由于我们只需要讨论偶数区间，则装桶应该分奇偶。

这里还有一个细节问题需要注意的是，我们枚举k的时候，这个非法区间里必须有k这个数，否则会算重贡献(比如非法区间2 4，枚举2的时候会算一次贡献，如果不进行去重的话，枚举3的时候又会算一次贡献，因为2满足<=3,所以k这个数字在这个区间内要有贡献的话，那么k必须是其左半边最大的数才行)

去重的方法很多，我这里使用的是二分去重，从左往右枚举右区间的同时把等式左边的值装进桶里，temp[i]表示前i个位置总共出现了temp[i]次k，然后存下这个值所对应的下标中k出现的次数temp[l]，枚举右区间时二分找到小于temp[r]的位置就是贡献数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
#define pii pair<int, int>
#define lowbit(x) (x & (-x))
void solve()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];int res = n * (n + 1) / 2;vector<int> c(n + 10, 0);for (int i = 1; i <= 10; i++){vector<int> temp(n + 10, 0);for (int j = 1; j <= n; j++){temp[j] = temp[j - 1];if (a[j] == i)temp[j]++;}for (int j = 1; j <= n; j++)c[j] += temp[j];map<int, vector<int>> s1, s2;for (int j = 1; j <= n; j++){int ned = 2 * c[j] - j;if (j & 1){s1[2 * c[j - 1] - j + 1].push_back(temp[j - 1]);int it = lower_bound(s2[ned].begin(), s2[ned].end(), temp[j]) - s2[ned].begin();res -= it;}else{s2[2 * c[j - 1] - j + 1].push_back(temp[j - 1]);int it = lower_bound(s1[ned].begin(), s1[ned].end(), temp[j]) - s1[ned].begin();res -= it;}}}cout << res << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--)solve();
}

查看全文

http://www.xdnf.cn/news/12624.html