【AtCoder Regular 119E】Pancakes 题解

题目大意

  给出一个序列 $a_1,\cdots,a_n$，你可以选择一段区间 $[l,r]$ 然后翻转 $a_l,\cdots,a_r$，使得 $\sum_{i=1}^{n-1} |a_i-a_{i+1}|$ 最小。

  $n \le 3\times 10^5,\ 1 \le a_i \le 10^9$
  2s

$$\\$$ $$\\$$ $$\\$$

题解

  首先翻转一段区间只有端点处会产生影响，影响是 $-|a_{l-1}-a_l|-|a_r-a_{r+1}|+|a_{l-1}-a_r|+|a_l-a_{r+1}|$。

  于是反手就是一个拆开绝对值+四个区域二维偏序。
  光荣 TLE

$$\\$$

  于是需要观察出一些额外的性质。
  就是如果 $a_{l-1} \le a_l$ 且 $a_r \ge a_{r+1}$，那么翻转 $[l,r]$ 必不会使答案更优。对称地，若 $a_{l-1} \ge a_l$ 且 $a_r \le a_{r+1}$，也不行。
  通过讨论可证。
  然后如果 $a_{l-1} \le a_l$ 且 $a_r \le a_{r+1}$，那么可以视为两个值域区间 $[a_{l-1},a_l],[a_r,a_{r+1}]$，于是翻转 $[l,r]$ 的收益就是这两个区间的交的长度的两倍。
  $a_{l-1} \ge a_l$ 且 $a_r \ge a_{r+1}$ 同理。

  所以现在问题转化成，给定若干个值域区间，求任意两个区间的交的最大长度。
  简单的 $O(n \log n)$ 数据结构即可。
  正着做一次再把序列反过来做一次。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;
typedef pair<int,int> pr;

const int maxn=3e5+5;
const int inf=2139062143;

int n,a[maxn];

int b[maxn],b0;
void discretize() {
	memcpy(b,a,sizeof(a));
	sort(b+1,b+1+n);
	b0=unique(b+1,b+1+n)-b-1;
	fo(i,1,n) a[i]=lower_bound(b+1,b+1+b0,a[i])-b;
}

int tr[4*maxn];
void tr_xg(int k,int l,int r,int x,int z) {
	if (l==r) {
		tr[k]=z;
		return;
	}
	int t=k<<1, mid=(l+r)>>1;
	if (x<=mid) tr_xg(t,l,mid,x,z); else tr_xg(t+1,mid+1,r,x,z);
	tr[k]=min(tr[t],tr[t+1]);
}

LL ans,organs;
vector<int> Q[maxn];
int cnt[maxn];
void solve() {
	fo(i,1,b0) Q[i].clear();
	fo(i,2,n) if (a[i-1]<a[i]) {
		cnt[a[i-1]]++;
		Q[a[i]].push_back(a[i-1]);
	}
	
	memset(tr,127,sizeof(tr));
	fo(i,1,b0) {
		if (cnt[i]) tr_xg(1,1,b0,i,i);
		for(int x:Q[i]) {
			if (--cnt[x]==0) tr_xg(1,1,b0,x,inf);
			int lp=max(tr[1],x);
			if (lp<=i) ans=min(ans,organs-2ll*(b[i]-b[lp]));
		}
	}
}

int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	
	fo(i,2,n) ans+=abs(a[i]-a[i-1]);
	organs=ans;
	fo(i,2,n-1) ans=min(ans,organs-abs(a[i]-a[i+1])+abs(a[1]-a[i+1]));
	fo(i,2,n-1) ans=min(ans,organs-abs(a[i]-a[i-1])+abs(a[n]-a[i-1]));
	
	discretize();
	solve();
	reverse(a+1,a+1+n);
	solve();
	
	printf("%lld\n",ans);
}