只要每一次将优先级最高的上面的物品移走，就一定能保证是最优解。
所以我们只要想办法简化这个模拟移物品的过程，看完了题解后，发现可以这么想，我们可以把两个栈头碰头的挨在一起，然后设一个指针代表两个栈的分界线，这样移动物品就变成了移动指针，而每一次移动的步数，就是指针和这个物品之间的距离。
开始的时候这个序列每一位都是1，然后如果删除了物品 i，就将 a[i] = 0，这样移动距离就是区间和了，然后用线段树维护即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter printf(" ") 13 #define space printf(" ") 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const int eps = 1e-8; 19 const int maxn = 1e5 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) 26 { 27 ans = ans * 10 + ch - '0'; ch = getchar(); 28 } 29 if(last == '-') ans = -ans; 30 return ans; 31 } 32 inline void write(ll x) 33 { 34 if(x < 0) x = -x, putchar('-'); 35 if(x >= 10) write(x / 10); 36 putchar(x % 10 + '0'); 37 } 38 39 int n1, n2, N; 40 ll a[maxn], t[maxn]; 41 int pos[maxn]; 42 43 int l[maxn << 2], r[maxn << 2], sum[maxn << 2]; 44 void build(int L, int R, int now) 45 { 46 l[now] = L; r[now] = R; 47 if(L == R) {sum[now] = 1; return;} 48 int mid = (L + R) >> 1; 49 build(L, mid, now << 1); 50 build(mid + 1, R, now << 1 | 1); 51 sum[now] = sum[now << 1] + sum[now << 1 | 1]; 52 } 53 void update(int id, int now) 54 { 55 if(l[now] == r[now]) {sum[now] = 0; return;} 56 int mid = (l[now] + r[now]) >> 1; 57 if(id <= mid) update(id, now << 1); 58 else update(id, now << 1 | 1); 59 sum[now] = sum[now << 1] + sum[now << 1 | 1]; 60 } 61 int query(int L, int R, int now) 62 { 63 if(l[now] == L && r[now] == R) return sum[now]; 64 int mid = (l[now] + r[now]) >> 1; 65 if(R <= mid) return query(L, R, now << 1); 66 else if(L > mid) return query(L, R, now << 1 | 1); 67 else return query(L , mid, now << 1) + query(mid + 1, R, now << 1 | 1); 68 } 69 70 ll ans = 0; 71 72 int main() 73 { 74 n1 = read(); n2 = read(); 75 N = n1 + n2; 76 for(int i = n1; i > 0; --i) a[i] = read(); 77 for(int i = n1 + 1; i <= N; ++i) a[i] = read(); 78 for(int i = 1; i <= N; ++i) t[i] = a[i]; 79 sort(t + 1, t + N + 1); //离散化优先级 80 for(int i = 1; i <= N; ++i) a[i] = lower_bound(t + 1, t + N + 1, a[i]) - t; 81 for(int i = 1; i <= N; ++i) pos[a[i]] = i; //记录每一个优先级所在位置 82 build(1, N, 1); 83 int x = pos[N] > n1 ? n1 + 1 : n1; //指针刚开始可以在n1处，也可以在n2处，需判断 84 for(int i = N; i > 0; --i) 85 { 86 if(pos[i] < x) ans += query(pos[i] + 1, x, 1); 87 else if(pos[i] > x) ans += query(x, pos[i] - 1, 1); 88 //一定要有if(pos[i] > x)，因为刚开始可能优先级最大的在栈顶，不需移动，否则会RE 89 x = pos[i]; //移动指针 90 update(x, 1); 91 } 92 write(ans); enter; 93 return 0; 94 }