01 串

二分转化为 01 串

如果某个问题满足：

• 如果序列只有 $\mathtt{0}$ 和 $\mathtt{1}$，问题是易解决的
• 答案依赖于序列中的数的大小关系
• 单次询问

可以考虑二分答案（或计算答案的中间变量）为 $x$，将序列中 $\geqslant x$ 的数置为 $1$，否则将 $<x$ 的数置为 $0$（或 $-1$，按需），将序列转化为 $\mathtt{01}$ 串。

【求中位数】$x = a'_{\frac{n+1}{2}}$，其中将 $a$ 数组排序后为 $a'$。$\geqslant x$ 的个数比 $< x$ 的个数 恰好 要多，因此可以通过二分出一个最大的满足上述整数得到中位数。值得注意的是，如果中位数定义为 $a_{\frac{n+1}{2}}$，将 $\geqslant x$ 的数置为 $1$，定义为 $a_{\frac{n}{2}}$，将 $> x$ 的数置为 $1$。

【求所有子序列的中位数】经典的 multiset 的 maintain 法，通常用于动态求中位数。时间复杂度 $\mathcal{O}[(n + q) \log V]$。

void eachT() {
    int n = read(), q = read();
    vector a(n, 0ll);
    map<ll, int> mp;
    for (int i = 0; i < n; i++) {
        a[i] = read();
    }

    multiset<ll> L;
    multiset<ll> R;
    ll mid = 0;

    auto maintain = [&] {
        if (L.size() == R.size() + 2) {
            R.insert(mid);
            L.erase(L.find(mid));
            mp[mid]--;
            mid = *L.rbegin();
        } else if (R.size() == L.size() + 1) {
            mid = *R.begin();
            R.erase(R.find(mid));
            mp[mid]++;
            L.insert(mid);
        }
    };

    for (int i = 0; i < n; i++) {
        if (a[i] > mid) {
            R.insert(a[i]);
        } else {
            L.insert(a[i]);
            mp[a[i]]++;
        }
        maintain();
    }

    while (q--) {
        int p = read();
        ll v = read();
        p--;

        ll pre = a[p];
        ll now = pre + v;
        a[p] = now;

        if (R.find(pre) != R.end()) {
            R.erase(R.find(pre));
        } else {
            L.erase(L.find(pre));
            mp[pre]--;
        }
        maintain();

        if (now > mid) {
            R.insert(now);
        } else {
            L.insert(now);
            mp[now]++;
        }
        maintain();

        int res = L.size();
        if (R.find(mid) != R.end()) {
            res -= mp[mid];
        }
        cout << res << "\n";
    }
}

【104901K】

• Problem
  • You can perform at most $K$ operations, where each operation can increase or decrease an element by 1.
  • Find the longest sub-interval where all elements become identical after the operations.
• Solution
  • The median is optimal.
  • Use two pointers + twin heaps to dynamically find the median.
  • Time complexity: $\mathcal{O}(N \log V)$.

【CF1935C】 给定 $L$，找出 $k$ 个二元组并重排，最大化 $k$ 使得：$\sum\limits_{i=1}^ka_i+\sum\limits_{i=1}^{k-1}|b_i-b_{i+1}| \leqslant L$。$n \leqslant 2000,\ 0 \leqslant a_{i},b_{i},l \leqslant 10^{9}$。

选定二元组后，$b$ 降序，原式化为 $\sum a_i+(b_k-b_1)\leqslant L$。枚举原有的 $b_{l}$​ 与 $b_{r}$​，然后贪心地从区间内选择较小的 $a$。用

int n = read(), L = read();
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
    a[i].second = read(), a[i].first = read();
}
sort(a.begin(), a.end());

int ans = 0;
for (int l = 0; l < n; ++l) {
    priority_queue<int> Q;
    int sum = 0;
    for (int r = l; r < n; ++r) {
        Q.push(a[r].second);
        sum += a[r].second;
        while (!Q.empty() && sum + a[r].first - a[l].first > L) {
            sum -= Q.top();
            Q.pop();
        }
        ans = max(ans, (int)Q.size());
    }
}
cout << ans << '\n';

【P2824】

• Problem
  • Given a permutation of $1$ to $N$.
  • Perform $Q$ operations, in each of which you are required to sort sub-intervals in ascending / descending order.
  • Finally, output the number at the $T$-th position.
• Solution
  • Binary search on the answer to transform the sequence into a $01$-string.
  • Sorting a $01$-string can be optimized using data structures to $\mathcal{O}(N+Q\log N)$.
  • Time complexity: $\mathcal{O}[(N+Q)\log^{2} N]$.

例 3 AGC006D. Median Pyramid Hard

![[Untitled/img/Pasted image 20240828155100.png]]

【VJwin6K】

• Problem
  • Given two sequences $A$ and $B$ of length $N$.
  • You can choose exactly one sub-interval and replace the elements of $A$ within this interval with the corresponding elements of $B$.
  • Output the maximum possible median of the final sequence $A$.
• Solution
  • Binary search on the answer $x$.
  • Define the initial contribution as $S = \sum [A_{i} \geqslant x]$. If an element $i$ is within the chosen sub-interval, its contribution change is:
    • $+1$ if $A_{i} < x$ and $B_{i} \geqslant x$
    • $-1$ if $A_{i} \geqslant x$ and $B_{i} < x$
    • $0$ otherwise
  • The problem reduces to finding the maximum subarray sum of these contribution changes to verify if $\max(S') > k$.
  • Time complexity: $\mathcal{O}(N \log V)$.

【CF1993D】

• Problem
  • You have to repeat the operation while $|A|>K$, where each operation can select any subarray of size $K$, then remove it.
  • Output the maximum possible median of the final sequence $A’$.

• Solution
  • Binary search on the answer $x$.
  • $|A'| = (|A|-1) \bmod K+1$.
  • The position of $A'_{i}$ in the original sequence $p_i \equiv i \pmod K$.
  • DP: $f_{i \bmod k}\leftarrow f_{i \bmod k-1}+A'_{i}$。
  • Time complexity: $\mathcal{O}(N \log V)$.

【CF2008H】

• Problem
  • Given a sequence $A$ of length $N$.
  • For each $K$, find the median of $\lbrace A_i \bmod K \rbrace$.
• Solution
  • Binary search on the answer $x$ to count how many elements satisfy $A_i \bmod K \leqslant x$.
  • $A_i \in [n K, n K + x], n=0,1,\dots,\lfloor \frac{V}{K} \rfloor$.
  • Time complexity: $\mathcal{O}\left(\log V\sum \frac{V}{K} \right) = \mathcal{O}(V\log^{2} V)$.

例 7 给定一个长度为 $n$ 的数组 $a$、一个一长度为 $n$ 的 01 数组 $b$ 和一个整数 $k$。最多可以执行以下操作 $k$ 次：选择一个索引 $i$，满足 $b_i = 1$，将 $a_i$ 增加 $1$。最大化 $\max\limits_{i = 1}^{n} \left(a_i + \operatorname{median}(c_i) \right)$，其中 $c_i$ 表示从 $a$ 中删除 $a_i$ 后得到的长度为 $n-1$ 的数组。$\operatorname{median}(p)$ 被定义为数组 $p$ 的第 $\left\lfloor \dfrac{|p|+1}{2} \right\rfloor$ 小元素。

Div2C 但是 1900，本题是经典 Hope to solve 的反例。不妨升序排序，那么答案是 $a_n + \operatorname{median}(a_{1}\sim a_{n-1})$。一种情形是操作指定的一个数 $k$ 次，如果 $b_{n}=0$，二分答案。

ll res = 0;
for (int i = 0; i < n; i++) {
    if (a[i][1] == 1) {
        res = max(res, 0ll + a[i][0] + k + (i < n / 2 ? a[n / 2][0] : a[n / 2 - 1][0]));
    }
}
if (a[n - 1][1] != 1) {
    auto check = [&](ll x) {
        int cnt = 0;
        priority_queue<int> Q;
        for (int i = 0; i < n - 1; i++) {
            if (a[i][0] >= x) {
                cnt++;
            } else if (a[i][1] == 1) {
                Q.push(a[i][0]);
            }
        }
        ll res = 0;
        while (cnt < (n - 1 - (n / 2 - 1))) {
            if (Q.empty()) {
                return true;
            }
            res += x - Q.top();
            Q.pop();
            if (res > k) {
                return true;
            }
            cnt++;
        }
        return false;
    };
    ll l = 0, r = 2e15;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    res = max(res, 0ll + r + a[n - 1][0]);
}
cout << res << endl;

CF2210E

CF2210E. Binary Strings are Simple?

• 交互。
• 猜测长度为 $N$ 的 01 串。
• 每次询问子串 $S[l\dots r]$，返回子串所有循环移位的逆序对数 mod 子串长度的集合大小。
• 询问的代价为 $\dfrac{N}{r-l+1}$，总询问代价不超过 $\max(30,3 N)$。
• 最多可以猜测 $2$ 次。

当循环左移 1 时贡献是 $-c_0=c_1-n$，否则是 $c_1$，逆序对在模意义下的增量总是 $c_1$。因此询问实际是 $\#\{x : x=kc_1\bmod N, k\in[1,N]\} = \displaystyle\frac{N}{\gcd(N,c_1)}$。

奇偶。在仅知道 $\gcd(N,c_{1})$ 与 $N$ 的前提下，若 $N$ 为偶数，则 $\gcd(N,c_{1})$ 的奇偶性与 $c_{1}$ 一致。

询问 $[l,i-1]$ 和 $[l,i+1]$（$l$ 是最小的让区间长度为偶数的值，有 $l\in\{1,2\}$），可以归纳由 $i$ 确定出 $i+1$。

允许猜 2 次，必然可以反推出做法是建立各个字符之间相同 / 不相同的关系，然后仅剩一个自由元再猜；接下来可以很自然地想到我们确定每两个相邻字符是相同或不同，并把第一个字符作为自由元。

左半段用前缀，右半段用后缀，代价是调和级数，