[ARC119E] Pancakes （二维偏序，分类讨论）
题面
一个长为
N
N
N 的序列
S
S
S ，最多翻转序列中一个区间，最小化
∑
i
=
2
N
∣
S
i
−
S
i
−
1
∣
\sum_{i=2}^{N}|S_i-S_{i-1}|
i=2∑N∣Si−Si−1∣
并输出这个值。
2
≤
N
≤
3
×
1
0
5
,
1
≤
S
i
≤
1
0
9
2\leq N\leq 3\times10^5,1\leq S_i\leq10^9
2≤N≤3×105,1≤Si≤109
题解
算是非常经典的一道题吧（ZYY金句）
我们发现翻转一个区间
[
l
,
r
]
[l,r]
[l,r] ，两边和中间的相邻数字差都不会变，只有左右端点附近会变，具体地，会令答案加上
∣
S
r
+
1
−
S
l
∣
+
∣
S
r
−
S
l
−
1
∣
−
(
∣
S
r
+
1
−
S
r
∣
+
∣
S
l
−
S
l
−
1
∣
)
|S_{r+1}-S_l|+|S_{r}-S_{l-1}|-(|S_{r+1}-S_{r}|+|S_l-S_{l-1}|)
∣Sr+1−Sl∣+∣Sr−Sl−1∣−(∣Sr+1−Sr∣+∣Sl−Sl−1∣)
这里有四个绝对值，后面两个绝对值分别与
r
r
r 和
l
l
l 单独相关，前面两个就得分类讨论了。
我们不妨令
S
r
+
1
=
x
,
S
r
=
y
,
S
l
=
a
,
S
l
−
1
=
b
S_{r+1}=x,S_r=y\;,\;S_l=a,S_{l-1}=b
Sr+1=x,Sr=y,Sl=a,Sl−1=b，那么前面两个绝对值就是
∣
x
−
a
∣
+
∣
y
−
b
∣
|x-a|+|y-b|
∣x−a∣+∣y−b∣
我们想得到这个减去
∣
x
−
y
∣
+
∣
a
−
b
∣
|x-y|+|a-b|
∣x−y∣+∣a−b∣ 的 最小值。
先鲁莽地讨论讨论（由于是取最值，下面全是可取等的也没问题了）：
x
≥
a
,
y
≥
b
:
(
x
+
y
)
−
(
a
+
b
)
x\geq a,y\geq b:~~~(x+y)-(a+b)
x≥a,y≥b: (x+y)−(a+b)
x
≥
a
,
y
≤
b
:
(
x
−
y
)
−
(
a
−
b
)
x\geq a,y\leq b:~~~(x-y)-(a-b)
x≥a,y≤b: (x−y)−(a−b)
x
≤
a
,
y
≥
b
:
(
y
−
x
)
−
(
b
−
a
)
x\leq a,y\geq b:~~~(y-x)-(b-a)
x≤a,y≥b: (y−x)−(b−a)
x
≤
a
,
y
≤
b
:
−
(
x
+
y
)
+
(
a
+
b
)
x\leq a,y\leq b:~~~-(x+y)+(a+b)
x≤a,y≤b: −(x+y)+(a+b)
然后我们其实没必要区分
(
x
,
y
)
(x,y)
(x,y) 和
(
a
,
b
)
(a,b)
(a,b) 的前后关系，因此其实可以省掉
c
a
s
e
3
、
4
\rm case~3、4
case 3、4 ，只讨论
1
、
2
1、2
1、2 。
分类讨论后，这其实就是个二维偏序。随便用什么数据结构或者直接
C
D
Q
\rm CDQ
CDQ 分治都行。
复杂度
O
(
N
log
N
)
O(N\log N)
O(NlogN) 。
CODE
#include<set>
#include<map>
#include<queue>
#include<ctime>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 300005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
#define eps 1e-9
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int a[MAXN],b[MAXN],a2[MAXN];
int Abs(int x) {return x < 0 ? -x:x;}
map<int,int> mp;
vector<int> bu[MAXN];
LL tre[MAXN<<2],M;
void maketree(int n) {M=1;while(M<n+2)M<<=1;for(int i = 1;i < (M<<1);i ++)tre[i]=1e18;}
void addtree(int x,LL y) {
int s=M+x;tre[s]=min(tre[s],y);s>>=1;
while(s)tre[s]=min(tre[s<<1],tre[s<<1|1]),s>>=1;
}
LL findtree(int l,int r) {
LL as = 1e18; if(l > r) return as;
int s = M+l-1,t = M+r+1;
while(s || t) {
if((s>>1) ^ (t>>1)) {
if(!(s & 1)) as = min(as,tre[s^1]);
if(t & 1) as = min(as,tre[t^1]);
}else break; s >>= 1;t >>= 1;
}return as;
}
int main() {
n = read();
LL sum = 0;
for(int i = 1;i <= n;i ++) {
a[i] = read();
if(i>1) sum += Abs(a[i]-a[i-1]);
b[i] = a[i];
}
sort(b + 1,b + 1 + n);
int nm = 0;
for(int i = 1;i <= n;i ++) {
if(i == 1 || b[i] > b[i-1]) mp[b[i]] = ++ nm;
}
LL asd = 0;
for(int i = 1;i <= n;i ++) {
a2[i] = mp[a[i]];
bu[a2[i]].push_back(i);
if(i < n) asd = min(asd,(LL)-Abs(a[i]-a[i+1])+Abs(a[i]-a[n]));
if(i > 1) asd = min(asd,(LL)-Abs(a[i]-a[i-1])+Abs(a[i]-a[1]));
}
maketree(nm);
for(int i = 1;i <= nm;i ++) {
for(int j = 0;j < (int)bu[i].size();j ++) {
int y = bu[i][j];
if(y > 1) {
LL fd = findtree(1,a2[y-1]) - Abs(a[y]-a[y-1]) + a[y] + a[y-1];
asd = min(asd,fd);
addtree(a2[y-1],(LL)-Abs(a[y]-a[y-1])-(a[y]+a[y-1]));
}
}
}
maketree(nm);
for(int i = 1;i <= nm;i ++) {
for(int j = 0;j < (int)bu[i].size();j ++) {
int y = bu[i][j];
if(y > 1) {
LL fd = findtree(a2[y-1]+1,nm) - Abs(a[y]-a[y-1]) + a[y] - a[y-1];
asd = min(asd,fd);
addtree(a2[y-1],(LL)-Abs(a[y]-a[y-1])-(a[y]-a[y-1]));
}
}
}
printf("%lld\n",sum+asd);
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章