首先来看暑假杭电多校的一道题目：
对于一个长度为 \(L\)(\(L\)为奇数) 的数组 \(a\)，定义它的中位数 \(median(a)\) 为 \(a\) 中第 \(\frac{L+1}{2}\) 大的数。现在给你一个长度为 \(n\) 的排列，对于每对满足 \(1\leq i \leq j \leq n\) 且 \(j-i \equiv 0 (mod 2)\) 的 \((i,j)\)，你需要计算 \(i*j*median(p[i,j])\)。输出所有值的和。
多测数 \(T \leq 20\)，排列长度 \(n \leq 2000\)。
对于这道题，首先想到的是枚举所有 \([i,j]\)，通过数据结构(对顶堆等)维护中位数。由于这些方法都带log，并且本题多测数据不保证 \(n\) 的总和。因此复杂度 \(O(n^2lognT)\)，无法通过本题。
换个思路，枚举区间不行，就计算每个位置的贡献。想想一个位置能成为一个区间的中位数，需要满足什么条件？该区间中大于它和小于它的数的数量相等。
一个很经典的处理就是，将小于 \(x\) 的数赋-1，将大于 \(x\) 的数赋1，我们对这个数组做前缀和，记作 \(pre\)。于是问题就转换为，在 \(x\) 的左边找到 \(pre_i\)，在 \(x\) 的右边找到 \(pre_j\)，使得 \(pre_i = pre_j\)。那么 \(pre_j - pre_i = 0\)，这就意味着，区间 \([l+1,r]\) 中大于 \(x\) 和小于 \(x\) 的数的数量相等。
对于每个数处理一次这样的前缀和数组是 \(O(n)\) 的，因此可以在 \(O(n^2T)\) 的时间下通过本题。
Code:
[code]#include #include using namespace std;using ll = long long;void solve(){ int n; cin >> n; vector a(n+10); for (int i = 1 ; i > a; ll ans = 0; for (int i = 1 ; i > n >> k; vector a(n+10); for (int i = 1 ; i > a; int ansl, ansr; auto check = [&](int mid) { vector sum(n+10); for (int i = 1 ; i = mid) sum++; else sum--; } int minn = 2e9; int l; for (int i = k ; i = 0) { ansl = l; ansr = i; return true; } } return false; }; int l = 0; int r = n + 1; while (l+1 != r) { int mid = (l+r) >> 1; if (check(mid)) l = mid; else r = mid; } check(l); cout > k; vector a(n+10); for (int i = 1 ; i > a; int ansl, ansr; auto check = [&](int mid) { vector sum(n+10); for (int i = 1 ; i = mid) sum++; else sum--; } int minn = 2e9; int l; for (int i = k ; i 0) { ansl = l; ansr = i; return true; } } return false; }; int l = 0; int r = n + 1; while (l+1 != r) { int mid = (l+r) >> 1; if (check(mid)) l = mid; else r = mid; } check(l); cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
