数据结构大🐂子题，很考验码力，虽然赛中不会做，但是把题解看懂不也是${\color{Red}win}?$

题目链接：Cut

题意

长度为$n$的序列$a_i$，$m$次操作，操作分三种

  • 将 $a_l,a_{l+1},\cdots,a_r$ 升序排列
  • 将 $a_l,a_{l+1},\cdots,a_r$ 降序排列
  • 求出下标在$[l,r]$内的最长奇偶交替子序列的长度

思路

看到区间排序，我们首先想到了这一道题P2824 [HEOI2016/TJOI2016]排序)，这题有两个做法，离线二分+线段树以及动态开点线段树+类似珂朵莉树的$set$操作。图片1

而这一题显然不能离线做，所以我们考虑用线段树分裂来维护区间排序操作。可以参考这位大佬的博客，[HEOI2016/TJOI2016]排序)。

然后我们怎么维护操作三的最长奇偶交替子序列的长度呢，如果单看操作三，我们可以用线段树维护区间合并，毕竟线段树很擅长区间信息合并这一操作，我们用$f_{i,j}$代表该区间以$i$开头，$j$结尾的最长奇偶交替序列长度

1
2
3
4
5
6
7
8
friend Info operator + (const Info &l, const Info &r) {
    Info rt;
    rt.f[0][0] = max({l.f[0][0], r.f[0][0], l.f[0][1] + r.f[0][0], l.f[0][0] + r.f[1][0]});
    rt.f[1][1] = max({l.f[1][1], r.f[1][1], l.f[1][0] + r.f[1][1], l.f[1][1] + r.f[0][1]});
    rt.f[1][0] = max({l.f[1][0], r.f[1][0], l.f[1][1] + r.f[0][0], l.f[1][0] + r.f[1][0]});
    rt.f[0][1] = max({l.f[0][1], r.f[0][1], l.f[0][0] + r.f[1][1], l.f[0][1] + r.f[0][1]});
    return rt;
}

然后我们思考如何将区间排序和操作三的查询结合在一起

图片2

这里我和题解不同，我是维护的右端点，但是结果是一样的，我们考虑将一段分裂的区间的信息全压缩到该区间的右端点上，每次分裂、合并时我们都用那颗维护操作三的线段树更新新区间右端点的$f_{i,j}$，查询时我们$Split(l-1),Split({r})$将$l-1,r$分裂成右端点，然后查询时我们只需要查询$[l,r]$里的右端点信息合并之后的最大值
$$
ans = \max (f_{0,0},f_{0,1},f_{1,0},f_{1,1})
$$

代码

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

struct Info {
    int f[2][2];
    Info() {
        f[0][0] = f[1][1] = f[0][1] = f[1][0] = -INF;
    }
    friend Info operator + (const Info &l, const Info &r) {
        Info rt;
        rt.f[0][0] = max({l.f[0][0], r.f[0][0], l.f[0][1] + r.f[0][0], l.f[0][0] + r.f[1][0]});
        rt.f[1][1] = max({l.f[1][1], r.f[1][1], l.f[1][0] + r.f[1][1], l.f[1][1] + r.f[0][1]});
        rt.f[1][0] = max({l.f[1][0], r.f[1][0], l.f[1][1] + r.f[0][0], l.f[1][0] + r.f[1][0]});
        rt.f[0][1] = max({l.f[0][1], r.f[0][1], l.f[0][0] + r.f[1][1], l.f[0][1] + r.f[0][1]});
        return rt;
    }
};
int tot, ls[N << 6], rs[N << 6], cnt[N << 6];
Info inf[N << 6];
set< int >::iterator it;
void push_up(int x) {
    cnt[x] = cnt[ls[x]] + cnt[rs[x]];
    inf[x] = inf[ls[x]] + inf[rs[x]];
}
void insert(int &x, int l, int r, int p) {
    x = ++ tot;
    cnt[x] = 1;
    inf[x].f[p & 1][p & 1] = 1;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
        insert(ls[x], l, mid, p);
    } else {
        insert(rs[x], mid + 1, r, p);
    }
}
void merge(int &x, int &y, int l, int r) {
    if (!x || !y) {
        x += y;
        return;
    }
    int mid = (l + r) >> 1;
    merge(ls[x], ls[y], l, mid);
    merge(rs[x], rs[y], mid + 1, r);
    push_up(x);
}
// 前k个给x,其余给y
void split(int p, int &x, int &y, int l, int r, int k) {
    if (!p) {
        x = y = 0;
        return;
    }
    if (l == r) { // 断边
        if (k) {
            x = p;
            y = 0;
        } else {
            y = p;
            x = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (cnt[ls[p]] >= k) { // 右儿子给y, 递归左儿子
        y = p;
        x = ++ tot;
        split(ls[p], ls[x], ls[y], l, mid, k);
    } else { // 左儿子给x, 递归右儿子
        x = p;
        y = ++ tot;
        split(rs[p], rs[x], rs[y], mid + 1, r, k - cnt[ls[p]]);
    }
    push_up(x);
    push_up(y);
}
Info seg[N << 2];
int n, q, a[N], col[N], rt[N];
set< int > s;
void update(int x, int l, int r, int p) {
    if (l == r) {
        seg[x] = inf[rt[l]];
        if (col[l]) {
            swap(seg[x].f[0][1], seg[x].f[1][0]);
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
        update(x << 1, l, mid, p);
    } else {
        update(x << 1 | 1, mid + 1, r, p);
    }
    seg[x] = seg[x << 1] + seg[x << 1 | 1];
}
Info query(int x, int l, int r, int ql, int qr) {
    if (ql > qr || ql > r || qr < l) {
        return Info();
    }
    if (ql <= l && r <= qr) {
        return seg[x];
    }
    int mid = (l + r) >> 1;
    return query(x << 1, l, mid, ql, qr) + query(x << 1 | 1, mid + 1, r, ql, qr);
}
void split(int p) {
    it = s.lower_bound(p);
    if (*it == p) {
        return;
    }
    int r = *it, l = *prev(it) + 1;
    if (col[r]) {
        split(rt[r], rt[r], rt[p], 1, n, r - p);
    } else {
        split(rt[r], rt[p], rt[r], 1, n, p - l + 1);
    }
    col[p] = col[r];
    update(1, 1, n, p);
    update(1, 1, n, r);
    s.insert(p);
}
void Sort(int l, int r, int op) {
    split(l - 1);
    split(r);
    int x = 0;
    for (it = s.lower_bound(l); *it <= r;) {
        merge(x, rt[*it], 1, n);
        rt[*it] = 0;
        update(1, 1, n, *it);
        set< int >::iterator IT = it;
        ++ it;
        s.erase(IT);
    }
    rt[r] = x;
    col[r] = op;
    s.insert(r);
    update(1, 1, n, r);
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> q;
    s.insert(0);
    s.insert(n + 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        s.insert(i);
        insert(rt[i], 1, n, a[i]);
        update(1, 1, n, i);
    }
    while (q -- ) {
        int op, l, r;
        cin >> op >> l >> r;
        -- op;
        if (op == 2) {
            split(l - 1);
            split(r);
            Info k = query(1, 1, n, l, r);
            cout << max({k.f[0][0], k.f[0][1], k.f[1][0], k.f[1][1]}) << '\n';
        } else {
            Sort(l, r, op);
        }
    }
    return 0;
}