[ICPC 2022 WF] Doing the Container Shuffle 题解

FFTotoro · 2025-09-01 17:27:46 · 题解

请注意文中“堆栈”和“卡车”的区别。

仔细分析一下这个调整栈顶的过程，根据期望的线性性，发现可以对于“每一段”过程分开计算：对于集装箱 a_i 和 a_{i+1}，考虑把 a_i 装入卡车后，期望有几个集装箱需要被调整，以使得 a_{i+1} 成为栈顶。

先考虑怎样的集装箱可能会在这个过程中被调整：只有 a_j(i+1<j\le n) 可能被调整（这些已经都装入卡车了），与此同时还需要满足 a_j>\min\{a_i,a_{i+1}\}（在它们之前装入堆栈的必然不会位于它们“中间”，也就不会被调整）。

接下来将证明每个满足以上条件的集装箱 a_j，都有恰好 \frac{1}{2} 的概率会位于 a_i 与 a_{i+1} 中间（会被调整）。将堆栈编号为 1 和 2，不妨认为 a_i<a_{i+1} 且 a_i 被装入了堆栈 1，分讨一下：

• 若 a_j<a_{i+1}（概率为 \frac{1}{2}），即 a_j 在 a_{i+1} 之前被装入堆栈：
  • 若 a_j 被装入堆栈 1，a_{i+1} 不管怎么放都会使 a_j 位于两者中间，概率为 \frac{1}{2}\times\frac{1}{2}=\frac{1}{4}；
  • 否则 a_{i+1} 不管怎么放都不会使 a_j 位于两者中间；
• 若 a_j>a_{i+1}（概率为 \frac{1}{2}），即 a_j 在 a_{i+1} 之后被装入堆栈：
  • 若 a_{i+1} 被装入堆栈 2，a_j 不管怎么放都会位于两者中间，概率为 \frac{1}{2}\times\frac{1}{2}=\frac{1}{4}；
  • 否则 a_j 不管怎么放都不会位于两者中间。

综上每个满足条件集装箱会在该过程中被调整的概率是 \frac{1}{2}。统计满足条件的集装箱个数是一个二维数点问题，可以使用树状数组维护，时间复杂度 O(n\log n)。

别忘了计算第一步移动时 a_1 顶上期望的集装箱个数（跟上面一样的方法）；最后答案还要记得 +n，因为装入卡车的操作数也要计入答案。

放代码：

#include<bits/stdc++.h>
using namespace std;
namespace IAOI_lib{
  template<typename T> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(int n):t(n){}
      int lowbit(int x){
        return x&-x;
      }
      void add(int p,T d){
        t[p++]+=d;
        while((p+=lowbit(p))<=t.size())t[p-1]+=d;
      }
      T pre_sum(int p){
        T s=t[p++];
        while((p-=lowbit(p))>0)s+=t[p-1];
        return s;
      }
      T sum(int l,int r){
        return pre_sum(r)-(l?pre_sum(l-1):0);
      }
  }; // 树状数组模板
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; long long c=0; cin>>n;
  vector<int> a(n);
  for(auto &i:a)cin>>i,i--;
  IAOI_lib::fenwick_tree<int> t(n);
  for(int i=n-1;i;i--)
    t.add(a[i],1),c+=t.sum(min(i>1?a[i-2]:n,a[i-1])+1,n-1);
    // 按照文中所述方法统计答案
  cout<<(c>>1)+n<<(c&1?".5":"")<<endl;
  return 0;
}