CF 2月部分题题解

CF 近期题解

鸽了好久，感觉还是多谢题解会更有提高

2056D

算法： 偏序，枚举，二值化(中位数的常见方法)， 前缀和

题意

求给定数组的所有子数组中，前中位数和后中位数相等的子数组的数量。数组值域\(\Omega\)为\(1 \sim 10\)。数组长\(10^5\)。

分析

由于值域很小，可以枚举中位数，将小于中位数的数赋值为\(-1\)，大于的赋值为\(1\)。
考虑某个区间小于,等于，大于所枚举的中位数的分别有\(l,m,r\)个，合法区间满足约束条件：
\[\begin{cases} l + m > r \\ r + m > l \\ \end{cases}\]

方法一：正向统计

由此我们得到了合法区间满足的两个偏序关系：
对区间\([1,i]\),令$ f_i = l + m - r , g_i = r + m - l$
对合法区间\([l,r]\)(l,r含义与前文不同，这里是区间端点)有偏序关系
\[\begin{cases} f_{l-1} < f_{r} \\ g_{l-1} < g_{r} \\ \end{cases}\]
于是我们事先计算好\(f,g\)数组，跑一个二维偏序即可。要注意的是这里的偏序是严格偏序，相等不能计入数量。
二维偏序可以树状数组/分治实现。
复杂度是\(O(\Omega n\log n)\)

template<typename T>
class bit //1 base
{
    int n;
    int upper;
    vector<T>tree;

    inline static const int lowbit(const int x)
    {
        return x & -x;
    }

public:
    bit(vector<T> a)
    {
        n = a.size() - 1;
        tree = a;
        for (int i = 1; i <= n; i++) {
            if (i + lowbit(i) <= n) {
                tree[i + lowbit(i)] += tree[i];
            }
        }
        upper = n;
        if (lowbit(upper) != upper) {
            while (upper != lowbit(upper)) {
                upper -= lowbit(upper);
            }
            upper <<= 1;
        }
    }

    void add(int p, T x)
    {
        while (p <= n) {
            tree[p] += x;
            p += lowbit(p);
        }
    }

    T qry(int r)
    {
        T res = 0;
        while (r != 0) {
            res += tree[r];
            r -= lowbit(r);
        }
        return res;
    }

    T qry(int l, int r)
    {
        if (l > 0)
            return qry(r) - qry(l - 1);
        else
            return qry(r);
    }

    int findleq(T v)const //前缀和小于等于的最大位置
    {
        int p = 0;
        T sum = 0;
        for (int len = upper; len != 0; len >>= 1) {
            if (len + p <= n && sum + tree[len + p] <= v) {
                p += len;
                sum += tree[p];
            }
        }
        return p;
    }

    int findl(T v)const //严格小的最大位置
    {
        int r = upper;
        int p = 0;
        T sum = 0;
        for (int len = upper; len != 0; len >>= 1) {
            if (len + p <= n && sum + tree[len + p] < v) {
                p += len;
                sum += tree[p];
            }
        }
        return p;
    }

    void clear()//
    {
        for (int i = 1; i <= n; i++) {
            tree[i] = 0;
        }
        return;
    }
};


void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ll ans = 0;

    for (int k = 1; k <= 10; k++) {
        vector<int>le(n + 1), re(n + 1);
        vector<pair<int, int>>pr(n + 1);
        for (int i = 1; i <= n; i++) {
            if (a[i] <= k) {
                le[i]++;
            }
            else {
                le[i]--;
            }
            if (a[i] >= k) {
                re[i]++;
            }
            else {
                re[i]--;
            }
            le[i] += le[i - 1];
            re[i] += re[i - 1];
            pr[i] = { le[i],re[i] };
        }
        sort(pr.begin(), pr.end());
        for (int i = 0; i <= n; i++) {//往右平移一段，去掉负值
            le[i] = pr[i].first + n + 1;
            re[i] = pr[i].second + n + 1;
        }
        bit<int>t(vector<int>(2 * n + 10));
        stack<int>s;
        int p = le[0];
        for (int i = 0; i <= n; i++) {
            if (le[i] > p) {
                while (!s.empty()) {
                    t.add(s.top(), 1);
                    s.pop();
                }
                p = le[i];
            }
            ans += t.qry(re[i] - 1);
            s.push(re[i]);
        }
    }
    cout << ans << endl;
    return;
}

方法二：逆向统计

我们可以考虑统计非法区间的数量，再用所有区间数量减去非法的得到合法的区间数量。
考虑非法区间的性质：一定存在一个数\(x\),使得区间中小于等于\(x\)的数和大于\(x\)的数数量相等。
那么我们可以用正向一样的前缀和方法来计算。
枚举数\(x\)，小于等于\(x\)的赋值为-1，大于\(x\)的赋值为1，设\(f\)为前缀和数组。那么非法区间\([l,r]\)有:
\[f[r] = f[l - 1]\]
具体做法是开一个数组\(cnt\)来统计\(f\)的值为\(k\)时,满足的数量。
然而，形如\([1,1,4,5,1,4]\)的区间，在\(x = 1,2,3\)时都会计入一次非法区间，会导致重复计数。重复计数后好像没有什么办法通过容斥减去重复，那么有没有办法避免重复呢?
一些非法区间有很多个\(x\)可以check到，但是这些\(x\)中只有最小的那个会在这个区间中出现！(可以check到的一定是连续的一些，下界一定出现在非法区间中)
那么我们计数的时候，只在\(x\)最小时计入数量，或者说只在\(x\)出现在这个区间时，我们才计入这个非法区间的贡献。
那么我们怎么确保我们统计的区间里面有\(x\)呢？回想我们前面的方法是对当前点\(r\),把\(cnt[f_r]\)作为以\(r\)为右端点的非法区间的数量。这里小于\(r\)的点都已经计入了\(cnt\)中。那么如果我们要求区间一定含有\(x\),那么在更改后的方法里，\(r\)到已经加入\(cnt\)的点之间必须有一个\(x\)。
所以我们一个考虑一个点何时加入到\(cnt\)中：从它本身开始(不包括本身)(因为作为左端点\(l\)时，表示的区间是从\(l+1\)开始的),直到遇到一个\(x\)，我们再把他加入到\(cnt\)中，那么对于所有的\(r\),我们在求解它时加入\(cnt\)的点至少和\(r\)之间有一个\(x\)。
而对于每个点，如果是\(x\)的话，我们应该先加入应该加入的点，再计算。
如果用数组统计的话，算法是线性的，时间复杂度为\(O(\Omega n)\)

void solve()
{
    ll n;
    cin >> n;
    vector<int>a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ll ans = n*(n+1)/2;
    for (int i = 1; i <= 10; i++) {
        vector<int>ps(n + 1);
        for (int j = 1; j <= n; j++) {
            if (a[j] <= i) 
                ps[j]++;
            else 
                ps[j]--;
            ps[j] += ps[j - 1];
        }
        map<int, ll>mp;
        stack<int>buf;
        for (int j = 0; j <= n; j++) {
            if (a[j] == i) {
                while (!buf.empty()) {
                    mp[buf.top()]++;
                    buf.pop();
                }
            }
            ans -= mp[ps[j]];
            buf.push(ps[j]);
        }
    }
    cout << ans << endl;
    return;

}

2057D

算法：偏序，线段树

题意

给一个数组。单点修改\(q\)次，每次求最大的 子数组极差减去子区间长度的值。
\(n,q = 10^5\)

分析

首先，子数组极差只取决于最大值或者最小值，那么如果答案取决于某个子数组，那么这个子数组的两端一定为最大值或者最小值，否则我们可以缩短这个子数组而不影响极差，使得答案变大。
这里我们就可以形式化地写出答案的形式：
\[ans = \max {(|a_r-a_l| - (r - l))}\]
但这还是很棘手，因为答案的两部分是分开的，没有联系起来。
很多时候，我们要求数组上一个某一个表达式的最值，都应该把这个表达式转化成只与某个点/区间端点单独决定的表达式，如某个点上的前缀和/差分/下标/点值以及它们的组合等等，而且在表达式中我们最好把与某个点相关的表达式放在一起组成一个整体。
如果我们确定一下\(a_r\)和\(a_l\)的大小关系，就可以去掉这个绝对值：
\[ans = \begin{cases} (a_r - r) - (a_l - l) & a_r \leq a_l \\ (a_l + l) - (a_r + r) & a_r \geq a_l \\ \end{cases}\] 定义\(f_i = a_i - i,g_i = a_i + i\)
这样，我们就可以把问题转化为找区间\([l,r]\)，使得\(f_r - f_l、 g_l- g_r\)最大。
直接暴力找是不行的，我们注意到一个区间只能有一个最小值和最大值，那么我们可以用一个分治算法来求解。对于\(f\)，算法的大概流程是：
1. 递归地求解左右子区间的最值和答案
2. 用右子区间\(f\)的最大值减去左子区间\(f\)的最小值作为答案，与左右子区间的答案取\(\max\)作为该区间的答案。

对于\(g\)的算法是类似的。
这个算法的复杂度是\(O(n\log n)\)。
但是我们还需要进行\(q\)次单点修改，求解的均摊时间不能超过\(O(\log n)\)
观察到每次修改单点，对于我们的分治算法，最多只有\(\log n\)个区间受到影响。这很像线段树的单点修改，而实际上我们的分治算法完全可以用一个线段树来实现，而单点修改就写一个线段树的单点修改就行。对于\(f,g\)，我们分别建两颗线段树即可(也可以一颗)。
最终的算法时间复杂度为\(O(n\log n)\)。

template <typename T>
class segtree //单点修改，区间查询max,min,以
{
    int n;
    vector<T>a;
    vector<T>tmax;
    vector<T>tmin;
    vector<T>ans1;
    vector<T>ans2;

public:
    segtree(vector<int>&a)
    {
        this->a = a;
        n = a.size();
        tmax.resize(n * 4 + 1);
        tmin.resize(n * 4 + 1);
        ans1.resize(n * 4 + 1);
        ans2.resize(n * 4 + 1);
        build(0, n - 1, 1);
    }

private:
    void pushup(int p)
    {
        tmax[p] = max(tmax[p * 2], tmax[p * 2 + 1]);
        tmin[p] = min(tmin[p * 2], tmin[p * 2 + 1]);
        ans1[p] = max(tmax[p * 2 + 1] - tmin[p * 2], max(ans1[p * 2], ans1[p * 2 + 1]));
        ans2[p] = max(tmax[p * 2] - tmin[p * 2 + 1], max(ans2[p * 2], ans2[p * 2 + 1]));
    }

    void build(int l, int r, int p)
    {
        if (l == r) {
            tmax[p] = tmin[p] = a[l];
            ans1[p] = ans2[p] = 0;
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, p * 2);
        build(m + 1, r, p * 2 + 1);
        pushup(p);
        return;
    }

    void update(int s, T val, int l, int r, int p)
    {
        if (l == r) {
            tmax[p] = tmin[p] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (s <= m) {
            update(s, val, l, m, p * 2);
            pushup(p);
        }
        else {
            update(s, val, m + 1, r, p * 2 + 1);
            pushup(p);
        }
    }

public:
    T get_ans1(void)
    {
        return ans1[1];
    }

    T get_ans2(void)
    {
        return ans2[1];
    }

    void modify(int p, T val)
    {
        update(p, val, 0, n - 1, 1);
    }
    
};

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int>a(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int>mima(n), mami(n);
    for (int i = 0; i < n; i++) {
        mima[i] = a[i] - i;
        mami[i] = a[i] + i;
    }
    segtree<int>t1(mima), t2(mami);
    cout << max(t1.get_ans1(), t2.get_ans2()) << endl;

    while (q--) {
        int p, x;
        cin >> p >> x;
        p--;
        t1.modify(p, x - p);
        t2.modify(p, x + p);
        cout << max(t1.get_ans1(), t2.get_ans2()) << endl;
    }
    return;
    
}

未完待续咕咕咕