「4th Ucup Stage 10」F. Foxes

    「4th Ucup Stage 10」F. Foxes

    QOJ 16005

    给出一个长度为 nn 的序列 a1,a2,…,ana_1, a_2, \dots, a_n。有一个指针 pp(初始时 p=1p = 1)。

    有 QQ 次操作,每次操作为以下三种之一:

    • <:令 p←p−1p \gets p - 1。
    • >:令 p←p+1p \gets p + 1。
    • ! v:令 ap←va_p \gets v,求出整个序列的严格最长上升子序列(LIS)。

    数据范围:2≤n≤2×1052 \leq n \leq 2\times 10^5,1≤Q≤5×1051 \leq Q \leq 5 \times 10^5,1≤ai,v≤1061\leq a_i, v \leq 10^6。

    时空限制:22s / 256256MiB。

    Solution

    从这个题吸取了一点教训:以往某些题的经验实在不一定管用。因为之前做 CF650D 的时候,并没有见到类似的做法,所以就以为不能这样维护。实际上这样做还是比较自然的,思维定式有点严重了。

    设 fif_i 表示以 ii 为结尾的 LIS 长度,gig_i 表示以 ii 为开头的 LIS 长度。

    则包含 pp 的全局 LIS 长度为 fp+gp−1f_p + g_p - 1,不包含 pp 的全局 LIS 长度为 max⁡x<p<y,ax<ay{fx+gy}\max\limits_{x < p < y, a_x < a_y} \{f_x + g_y\}。

    由于每次指针 pp 移动的步长为 11,所以我们可以动态地将 f[1,p−1]f_{[1, p - 1]} 以及 g[p+1,n]g_{[p + 1, n]} 维护出来。虽然每次修改 apa_p 会影响所有的 g[1,p−1]g_{[1, p - 1]} 与 f[p+1,n]f_{[p + 1, n]},但在求解答案的时候,我们只关心 f[1,p−1]f_{[1, p - 1]} 和 g[p+1,n]g_{[p + 1, n]}。所以我们只需在移动指针的过程中,顺带求出新的 fp,gpf_p, g_p 即可(没有遍历到的点暂且不会对答案产生影响)。

    回到如何求解答案,我们开一个值域线段树维护 f[1,p−1]f_{[1, p - 1]} 与 g[p+1,n]g_{[p + 1, n]}(以 aia_i 为下标)。

    包含 pp 的全局 LIS 长度 fp+gp−1f_p + g_p - 1 是好求的。

    不包含 pp 的全局 LIS 长度 max⁡ax<ay{fx+gy}\max\limits_{a_x < a_y} \{ f_x + g_y \} 可以在线段树上传信息的时候顺带求出。请注意这里我们动态维护出了 f[1,p−1]f_{[1, p - 1]} 与 g[p+1,n]g_{[p + 1, n]},所以自然可以去掉 x<p<yx < p < y 的限制。

    时间复杂度 O((n+Q)log⁡n)\mathcal{O}((n + Q) \log n)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 200100;
    
    const int sup = 1000001;
    const int SIZE = 1000100;
    
    int n, Q;
    int a[N];
    
    int f[N], g[N];
    
    std::multiset<int> fv[SIZE], gv[SIZE];
    
    namespace SGT {
        struct node {
            int f, g;
            int ans;
        } t[SIZE * 4];
    
        void upd(int p) {
            t[p].f = std::max(t[p * 2].f, t[p * 2 + 1].f);
            t[p].g = std::max(t[p * 2].g, t[p * 2 + 1].g);
            t[p].ans = std::max(std::max(t[p * 2].ans, t[p * 2 + 1].ans), t[p * 2].f + t[p * 2 + 1].g);
        }
    
        void change(int p, int l, int r, int x, int y, int opt, int type) {
            if (l == r) {
                if (type == 1) {
                    opt == +1 ? fv[l].insert(y) : fv[l].erase(fv[l].find(y));
                    t[p].f = fv[l].empty() ? 0 : *(-- fv[l].end());
                } else {
                    opt == +1 ? gv[l].insert(y) : gv[l].erase(gv[l].find(y));
                    t[p].g = gv[l].empty() ? 0 : *(-- gv[l].end());
                }
                t[p].ans = std::max(t[p].f, t[p].g);
                return;
            }
            int mid = (l + r) >> 1;
            if (x <= mid) {
                change(p * 2, l, mid, x, y, opt, type);
            } else {
                change(p * 2 + 1, mid + 1, r, x, y, opt, type);
            }
            upd(p);
        }
        void change(int x, int y, int opt, int type) {
            change(1, 0, sup, x, y, opt, type);
        }
    
        int ask(int p, int l, int r, int s, int e, int type) {
            if (s <= l && r <= e) {
                return type == 1 ? t[p].f : t[p].g;
            }
            int mid = (l + r) >> 1;
            if (s <= mid && mid < e) {
                return std::max(ask(p * 2, l, mid, s, e, type), ask(p * 2 + 1, mid + 1, r, s, e, type));
            }
            if (s <= mid) {
                return ask(p * 2, l, mid, s, e, type);
            } else {
                return ask(p * 2 + 1, mid + 1, r, s, e, type);
            }
        }
        int ask(int s, int e, int type) {
            return ask(1, 0, sup, s, e, type);
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> Q;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
    
        for (int i = n; i >= 2; i --) {
            g[i] = SGT::ask(a[i] + 1, sup, 2) + 1;
            SGT::change(a[i], g[i], +1, 2);
        }
        f[1] = 1;
    
        int p = 1;
        while (Q --) {
            std::string str;
            std::cin >> str;
    
            if (str == ">") {
                SGT::change(a[p], f[p], +1, 1);
                SGT::change(a[p + 1], g[p + 1], -1, 2); 
                p ++;
                f[p] = SGT::ask(0, a[p] - 1, 1) + 1;
            } else if (str == "<") {
                SGT::change(a[p - 1], f[p - 1], -1, 1);
                SGT::change(a[p], g[p], +1, 2);
                p --;
                g[p] = SGT::ask(a[p] + 1, sup, 2) + 1;
            } else {
                int y;
                std::cin >> y;
                
                a[p] = y;
                f[p] = SGT::ask(0, y - 1, 1) + 1;
                g[p] = SGT::ask(y + 1, sup, 2) + 1;
    
                int ans1 = f[p] + g[p] - 1;
                int ans2 = SGT::t[1].ans;
    
                std::cout << std::max(ans1, ans2) << '\n';
            }
        }
    
        return 0;
    }
    
    /*
    5 2
    3 4 1 7 2
    >
    ! 2
    
    5 8
    3 4 1 7 2
    >
    ! 2
    >
    >
    >
    ! 10
    <
    ! 11
    */