「LibreOJ Round #6」花火

题目描述#

「Hanabi, hanabi……」
一听说祭典上没有烟火，Karen 一脸沮丧。
「有的哦…… 虽然比不上大型烟花就是了。」
还好 Shinobu 早有准备，Alice、Ayaya、Karen、Shinobu、Yoko 五人又能继续愉快地玩耍啦！
「噢……！不是有放上天的烟花嘛！」Karen 兴奋地喊道。
「啊等等……」Yoko 惊呼。Karen 手持点燃引信的烟花，「嗯？？」
Yoko 最希望见到的是排列优美的烟火，当然不会放过这个机会…… 不过时间似乎已经不多了。

$n$ 个烟火排成一排，从左到右高度分别为 $h_1, h_2, \cdots, h_n$ ，这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。
每次 Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换，使这些烟火从左到右的高度递增。

输入格式#

第一行包含一个正整数 $n$ 。
第二行包含 $n$ 个正整数 $h_1, h_2, \cdots, h_n$ ，相邻整数之间用一个空格隔开。

输出格式#

输出一个整数，表示最少的交换次数。

样例#

样例输入#

样例输出#

1
5

样例解释#

一开始， $5$ 个烟火的高度依次为 $3,5,4,1,2$ 。
第 $1$ 次，交换第 $4$ 根烟火和第 $5$ 根烟火，交换后烟火的高度依次为 $3,5,4,2,1$ 。
第 $2$ 次，交换第 $3$ 根烟火和第 $4$ 根烟火，交换后烟火的高度依次为 $3,5,2,4,1$ 。
第 $3$ 次，交换第 $1$ 根烟火和第 $2$ 根烟火，交换后烟火的高度依次为 $5,3,2,4,1$ 。
第 $4$ 次，交换第 $2$ 根烟火和第 $3$ 根烟火，交换后烟火的高度依次为 $5,2,3,4,1$ 。
第 $5$ 次，交换第 $1$ 根烟火和第 $5$ 根烟火，交换后烟火的高度依次为 $1,2,3,4,5$ 。
可以证明这是交换次数最少的方案。

数据范围与提示#

对于所有数据，满足 $1 \leq n \leq 300,000, 1 \leq h_i \leq n, h_i$ 互不相同。

Subtask #	分值	$n$
1	$6$	$\leq 4$
2	$11$	$\leq 8$
3	$16$	$\leq 100$
4	$8$	$\leq 300$
5	$13$	$\leq 700$
6	$7$	$\leq 2,000$
7	$6$	$\leq 6,000$
8	$14$	$\leq 60,000$
9	$19$	$\leq 300,000$

题解#

Subtask 1 & 2#

直接去搜吧，记忆化一下
因为与 $DP$ 没关系，就不写了

Subtask 3#

需要一个多项式复杂度的做法
我们可以证明

总是可以假设交换不相邻元素在第一次进行。
证明: 假设交换的两个值为 $x$ 和 $y$ 那么，我们可以在第一次就交换他们然后可以构造出一个与原先交换次数相同的解
如果已经交换了不相邻元素，之后的最小交换次数等于此时排列的逆序对数。
证明: 设这一次交换的数为 $h[i]$ 与 $h[i + 1]$ 则这一次交换后他们与其他数 $(j \neq i, j \neq i + 1)$ 的逆序对数是不变的。那么改变的只有他们之间的关系。又因为一个含有逆序对的数列中一定存在 $h[i] > h[i + 1]$ 所以只有不断的找到这样的数对交换即可，每次交换减少一个逆序对，交换次数为逆序对数。

可以 $n^2$ 枚举第一次交换的两个数，然后 $n^2$ 求逆序对
时间复杂度 $O(n^4)$
33pts

Subtask 4#

与上面的相同，只是用随便的一些方法将逆序对用 $n \log(n)$ 求
41pts

Subtask 5#

这时我们需要一个 $O(n^3)$ 的做法
因为每次交换所改变的逆序对数很少，只要先求出来再 $O(n)$ 维护即可
54pts

Subtask 6 & 7#

每次改变的逆序对并不用 $O(n)$ 求
将 $(x, h_x)$ 看做平面上的点
在第一次交换的时候，只有当 $h[i] > h[j]$ 时才有意义
然后我们发现这时减少的逆序对数就是以 $(i, h[i])$ 为左上角 $(j, h[j])$ 为右下角的矩形内部点数的二倍
然后用一个二维前缀和就可以了
67pts

Subtask 8 & 9#

到这里其实就比较显然了
我们想要找的是一对点作为左上角与右下角使得其矩形内的点数最多。
这显然和我们做过的一道题一样，然后用线段树维护就好了
时间复杂度 $O(n\log(n))$
~~不知道为什么我的程序又长又慢 2333~~
知道了，我作死用的平衡树。。。

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <set>
5
using namespace std;
6
inline int read()
7
{
8
    int x=0,f=1;char ch=getchar();
9
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11
    return x*f;
12
}
13
const int MAXN = 300005;
14
#define size(_) ((_) ? (_)->s : 0)
15
#define _Max(_) ((_) ? (_)->Max : 0)
16
struct Node
17
{
18
    Node *ch[2];
19
    int s, v, key;
20
    int val, Max, lazy;
21
    Node(int x)
22
    {
23
        s = 0, v = x;
24
        key = rand();
25
        val = lazy = Max = 1;
26
        ch[0] = ch[1] = NULL;
27
    }
28
    void Pushup()
29
    {
30
        s = size(ch[0]) + size(ch[1]) + 1;
31
        Max = max(max(_Max(ch[0]), _Max(ch[1])), val);
32
    }
33
    void Pushlazy(int x)
34
    {
35
        val += x;
36
        lazy += x;
37
        Max += x;
38
    }
39
    void Pushdown()
40
    {
41
        if (lazy)
42
        {
43
            if (ch[0]) ch[0]->Pushlazy(lazy);
44
            if (ch[1]) ch[1]->Pushlazy(lazy);
45
            lazy = 0;
46
        }
47
    }
48
}*root;
49
Node *Merge(Node *A, Node *B)
50
{
51
    if (!A) return B;
52
    if (!B) return A;
53
    if (A->key < B->key)
54
    {
55
        A->Pushdown();
56
        A->ch[1] = Merge(A->ch[1], B);
57
        A->Pushup();
58
        return A;
59
    }
60
    else
61
    {
62
        B->Pushdown();
63
        B->ch[0] = Merge(A, B->ch[0]);
64
        B->Pushup();
65
        return B;
66
    }
67
}
68
typedef pair<Node*, Node*> DNode;
69
DNode Split(Node *rt, int k)
70
{
71
    if (!rt) return DNode(NULL, NULL);
72
    DNode o;
73
    rt->Pushdown();
74
    if (size(rt->ch[0]) >= k)
75
    {
76
        o = Split(rt->ch[0], k);
77
        rt->ch[0] = o.second;
78
        rt->Pushup();
79
        o.second = rt;
80
    }
81
    else
82
    {
83
        o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
84
        rt->ch[1] = o.first;
85
        rt->Pushup();
86
        o.first = rt;
87
    }
88
    return o;
89
}
90
int Rank(Node *rt, int x)
91
{
92
    if (!rt) return 0;
93
    return x <= rt->v ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
94
}
95
void Insert(int x)
96
{
97
    int k = Rank(root, x);
98
    DNode y = Split(root, k);
99
    Node *n = new Node(x);
100
    root = Merge(y.first, Merge(n, y.second));
101
}
102
void Update(int x, int c)
103
{
104
    int k = Rank(root, x);
105
    DNode y = Split(root, k);
106
    if (y.second) y.second->Pushlazy(c);
107
    root = Merge(y.first, y.second);
108
}
109
void Update(int l, int r, int c)
110
{
111
    int k = Rank(root, l);
112
    DNode x = Split(root, k);
113
    int k2 = Rank(x.second, r + 1);
114
    DNode y = Split(x.second, k2);
115
    if (y.first) y.first->Pushlazy(c);
116
    root = Merge(x.first, Merge(y.first, y.second));
117
}
118
int Calc_Max(Node *rt)
119
{
120
    if (!rt->ch[1]) return rt->v;
121
    else return Calc_Max(rt->ch[1]);
122
}
123
int Query(int x)
124
{
125
    int k = Rank(root, x);
126
    DNode y = Split(root, k);
127
    int ans = _Max(y.second);
128
    root = Merge(y.first, y.second);
129
    return ans + 1;
130
}
131
set<int> t1, t2;
132
struct data
133
{
134
    int v, id, Mx;
135
    bool operator < (const data &a) const
136
    {
137
        return v < a.v;
138
    }
139
};
140
set<data> t3;
141
int n;
142
int a[MAXN], b[MAXN];
143
long long S[MAXN];
144
#define lowbit(_) ((_) & (-_))
145
void add(int x, int c)
146
{
147
    for (int i = x; i <= n; i += lowbit(i))
148
        S[i] += c;
149
}
150
long long Q(int x)
151
{
152
    long long ans = 0;
153
    for (int i = x; i >= 1; i -= lowbit(i))
154
        ans += S[i];
155
    return ans;
156
}
157
int st1[MAXN], st2[MAXN], top1, top2;
158
int main()
159
{
160
    // freopen ("columns3_2.in", "r", stdin);
161
    // freopen ("columns.out", "w", stdout);
162
    n = read();
163
    for (int i = 1; i <= n; i++)
164
        b[i] = a[i] = read();
165
    sort(b + 1, b + n + 1);
166
    for (int i = 1; i <= n; i++)
167
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
168
    long long Sum = 0;
169
    for (int i = 1; i <= n; i++)
170
        Sum += Q(n) - Q(a[i]), add(a[i], 1);
171
    st1[++top1] = 1;
172
    t1.insert(1);
173
    for (int i = 2; i <= n; i++)
174
        if (a[i] > a[st1[top1]])
175
            st1[++top1] = i, t1.insert(i);
176
    st2[++top2] = n;
177
    t2.insert(n);
178
    for (int i = n - 1; i >= 1; i--)
179
        if (a[i] < a[st2[top2]])
180
            st2[++top2] = i, t2.insert(i);
181
    reverse(st2 + 1, st2 + top2 + 1);
182
    int ans = 0;
183
    for (int i = 1; i <= n; i++)
184
    {
185
        if (!t1.count(i) && !t2.count(i))
186
        {
187
            Update(a[i], 1);
188
            t3.insert((data){a[i], i, Calc_Max(root)});
189
        }
190
        else
191
        {
192
            if (t1.count(i))
193
                Insert(a[i]);
194
            if (t2.count(i))
195
            {
196
                for (auto x : t3)
197
                    if (x.v > a[i]) break;
198
                    else
199
                        Update(x.v, x.Mx, -1);
200
                auto x2 = t3.begin();
201
                if (x2 != t3.end()) x2++;
202
                for (auto x = t3.begin(); x != t3.end(); )
203
                {
204
                    if (x->v > a[i]) break;
205
                    else
206
                        t3.erase(x);
207
                    x = x2;
208
                    if (x2 != t3.end())
209
                        x2++;
210
                }
211
                ans = max(ans, Query(a[i]));
212
            }
213
        }
214
    }
215
    printf ("%lld\n", min(Sum, Sum - (ans - 2) * 2));
216
}