「4th Ucup Stage 10」F. Foxes

发表于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

Description

Link：QOJ 16005

给出一个长度为 nn 的序列 a1,a2,⋯ ,ana_1, a_2, \cdots, 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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#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 = 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
*/