题目
Description 妖梦在练习剑术 有 n 个木桩排成一排，从左到右高度分别为 h 1 ,h 2 ,h 3 ,…,h n ，这些高度两两不同 妖梦每次可以选择两个相邻的木桩交换，这样的交换可以进行任意多次 妖梦也可以使用符卡：选择两个木桩交换，但最多只能使用一次。 妖梦想要知道将木桩排成从左到右递增的顺序，她最少需要进行多少次交换。
Input 从 sword.in 中读入数据 第一行一个正整数 n 第二行 n 个正整数 h 1 ,h 2 ,…,h n
Output 输出到文件 sword.out 中 一行一个整数，表示最少的交换次数
Sample Input 5 3 5 4 1 2
Sample Output 5
Data Constraint
Hint (3,5,4,1,2) 交换 1,2 (3,5,4,2,1) 交换 3,4 (3,5,2,4,1) 交换 3,5 (5,3,2,4,1) 交换 2,3 (5,2,3,4,1) 交换 1,5 (1,2,3,4,5) 可以证明这是次数最少的方法
思路
容易发现最优解满足 h[i] 是前缀最大值且 h[j] 为后缀最小值 不妨反过来考虑每个 x 对哪些 (i,j) 有贡献 令 l 为最小的满足 h[l]>h[x] 且 h[l] 为前缀最大值的 l,h[r] 为最大 的满足 h[r]<h[x] 且 h[r] 为后缀最小值的 r 那么 x 的贡献就是 i ∈ [l, x − 1], j ∈ [x + 1,r] 这样一个矩形 问题变为矩形加全局最大值，离线扫描线维护即可 复杂度 O(n log n)
代码
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define N 300005
int L
,R
,n
,yjy
,g
,ta
,tb
,cnt
,a
[N
],A
[N
],B
[N
],s
[N
],t
[N
];
void add(int x
,int p
) {
for(; x
<= n
; x
+= x
& -x
) s
[x
] += p
;
}
int que(int x
) {
int g
= 0;
for(; x
; x
-= x
& -x
) g
+= s
[x
];
return g
;
}
int F(int x
,int y
) {
while(R
< y
) add(a
[++R
],1);
while(R
> y
) add(a
[R
--],-1);
while(L
< x
) add(a
[L
++],-1);
while(L
> x
) add(a
[--L
],1);
return que(a
[x
]) + que(a
[x
] - 1) - que(a
[y
]) - que(a
[y
] - 1) - 2;
}
void work(int l
,int r
,int ql
,int qr
) {
if (l
> r
|| ql
> qr
)
return;
int mid
= l
+ r
>> 1,p
= 0,g
= -1e18,t
;
for(int i
= ql
; i
<= qr
; i
++)
if (A
[i
] != B
[mid
])
if (g
< (t
= F(A
[i
],B
[mid
])))
g
= t
,p
= i
;
yjy
= max(yjy
,g
);
work(l
,mid
- 1,ql
,p
);
work(mid
+ 1,r
,p
,qr
);
}
signed main() {
freopen("sword.in","r",stdin); freopen("sword.out","w",stdout);
scanf("%lld",&n
);
bool bz
=1;
for(int i
= 1; i
<= n
; i
++)
{
scanf("%lld",&a
[i
]),t
[i
] = a
[i
];
if(a
[i
]<a
[i
-1]) bz
=0;
}
if(bz
)
{
printf("0"); return 0;
}
sort(t
+ 1,t
+ 1 + n
);
cnt
= unique(t
+ 1,t
+ 1 + n
) - t
- 1;
for(int i
= 1; i
<= n
; i
++) a
[i
] = lower_bound(t
+ 1,t
+ 1 + cnt
,a
[i
]) - t
;
for(int i
= 1; i
<= n
; i
++) g
+= i
- 1 - que(a
[i
]),add(a
[i
],1);
if (!g
) {
puts(cnt
== n
? "1" : "0");
return 0;
}
for(int i
= 1; i
<= n
; i
++)
if (!ta
|| a
[i
] > a
[A
[ta
]])
A
[++ta
] = i
;
for(int i
= n
; i
>= 1; i
--)
if (!tb
|| a
[i
] < a
[B
[tb
]])
B
[++tb
] = i
;
reverse(B
+ 1,B
+ tb
+ 1);
L
= 1,R
= 0;
yjy
= -1e18;
memset(s
,0,sizeof(s
));
work(1,tb
,1,ta
);
printf("%lld\n",g
- yjy
);
}
