官方题解。来源：清华大学学生算法协会仓库

给定三种记号：

• $s_i\text{#}s_{i+1}$ 表示读完 $s_i$ 后应紧跟 $s_{i+1}$，且优先级高于其它两种符号；
• $s_i\text{*}s_{i+1}$ 表示读完 $s_{i+1}$ 后再读 $s_i$；
• $s_i\text{p-q}$ 表示（在不考虑的情况下）（如果有则）先读对应的 $\text{p-(q-1)}$ 前的文字，读完 $s_i$，再读对应的 $\text{p-(q+1)}$ 前的文字。

给出一个排列 $p_i$，求一组记号使得阅读 $p_i$ 的顺序恰好将其还原为 $1 \sim K$ 的排列。

$1 \le K \le 10^6$

先考虑只有最复杂的 $\text{p-q}$ 时应该怎么处理。

可以想到用栈来保存当前的遥远跳转结构，如果碰到可以直接阅读的则将栈清空。

如果有多个遥远跳转结构怎么办？栈套栈！每弹出一个栈，更新新栈顶的栈的嵌套层数。

在此基础上可以实现另外两种符号，其中 $\text{*}$（及其连续段）需要根据头尾情况简单分类讨论一下。想清楚了实现起来并不复杂。

复杂度 $O(K)$

#include<bits/stdc++.h>
using namespace std;
long long n,a[500005],k,b[500005];
long long q[500005],l,r;
bool cmp(long long x,long long y){
  return x>y;
}
struct NODE {
  int idx;
  long long num;
};
deque<NODE> dq;
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  sort(a+1,a+n+1,cmp);
  if(k==2){
    long long minn=1e16;
    for(int i=1;i<n;i++){
      minn=min(a[i]-a[i+1],minn);
    }
    cout<<minn*minn;return 0;
  }
  long long ans=1e16;
  for(int i=1;i<=n;i++){
    if(a[i]==a[i+1]){          
      cout<<0;return 0;
    }
  }
  for(int i=1;i<=n;i++){
    b[i]=a[i]-a[i+1];
    if(i==n)b[i]=a[i-1]-a[i];
  }

  for (int i = 1; i <n; ++i) {
    while (!dq.empty() && i - dq.front().idx >= k-1) dq.pop_front();
    while ((!dq.empty() && b[i] < dq.back().num) || (int) dq.size() == k-1) dq.pop_back();
    dq.push_back({i, b[i]});
    if (i >= k-1) {
      ans=min(ans,dq.front().num*(a[i-k+2]-a[i+1]));
    }
  }
  cout<<ans;
  return 0;
}