ACSX: Jan&Feb, 2023

飞花

有 \(n(n\le 2\times 10^5)\) 张卡牌，正面 \(a_i\)，反面 \(b_i\)，所有 \(1\le a_i,b_i\le 2n\) 且互不相同。
你可以选择翻任意张卡牌，翻完后可不耗代价任意重排，问最少翻多少张牌，使得最后有 \(a_1<a_2<a_3<...<a_n\) 且 \(b_1>b_2>b_3>...>b_n\)？

首先有个小性质一定得把握到，这是突破口：若存在 \(a_i>n,b_i>n\) 则一定无解（原因是若存在这样的一组则必存在一组都小于等于 n 的，这两个不可能形成答案的pattern）
有了这个那就是说每一张牌都是一个在 [1,n] 一个在 [n+1,2n]，那么都好做了。这样显然按照较小面递增的顺序排列就需要得到两个降序列，第一个不再翻，第二个再翻一次接到右边。也就是问题转化为一个数组 \(\{A_n\}\)，有两个初始为正无穷的降序列，每个元素放到0序列末端需要支付0/1的代价，放到1序列末端需要支付0/1的代价（钦定0序列是后来不再翻的，1序列是后来再翻的），需要保证是降序列，最小代价是多少。

显然的 DP，设 \(f(i,j,0/1)\) 表示到 \(i\)，\(j\) 为“另一个序列”的末数值，\(A_i\) 放到哪个序列，的最小代价。
if(a[i+1]<a[i]) f[i+1][x][0]<----f[i][x][0]+[a[i+1]已翻转]，f[i+1][x][1]<---f[i][x][1]+[a[i+1]未翻转]
f[i+1][a[i]][0]<----f[i][x>a[i+1]][1]+[a[i+1]已翻转]，f[i+1][a[i]][1]<----f[i][x>a[i+1]][0]+[a[i+1]未翻转]

使用线段树维护转移。注意如果 a[i+1]>a[i] 的话是要清空线段树的（全设成INF），然后线段树是单点修改查区间最小值。