题目内容游游有两个长度同为nnn的整数数组aaa和bbb。她会对数组aaa执行标准冒泡排序来将其排成非递减序列数组bbb始终不变对于i1,2,…,n−1i 1,2,\dots,n-1i1,2,…,n−1依次执行一趟扫描在第iii趟中按顺序检查j1,2,…,n−ij 1,2,\dots,n-ij1,2,…,n−i若当前ajaj1a_j a_{j1}aj​aj1​则交换这两个元素否则不交换。每次实际发生交换时其代价由当前位置对应的固定值bj,bj1b_j,b_{j1}bj​,bj1​决定若bj≥bj1b_j \ge b_{j1}bj​≥bj1​则这次交换代价为000若bjbj1b_j b_{j1}bj​bj1​则这次交换代价为111。请你计算按照上述固定的冒泡排序过程把数组aaa排成非递减后所有交换操作的总代价。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤105)T(1 \le T \le 10^5)T(1≤T≤105)代表数据组数。每组测试数据描述如下第一行输入一个整数n(1≤n≤2×105)n(1 \le n \le 2 \times 10^5)n(1≤n≤2×105)。第二行输入nnn个整数a1,a2,…,an(∣ai∣≤109)a_1,a_2,\dots,a_n(|a_i| \le 10^9)a1​,a2​,…,an​(∣ai​∣≤109)。第三行输入nnn个整数b1,b2,…,bn(∣bi∣≤109)b_1,b_2,\dots,b_n(|b_i| \le 10^9)b1​,b2​,…,bn​(∣bi​∣≤109)。保证单个测试文件中所有测试数据的nnn之和不超过5×1055 \times 10^55×105。输出描述对于每组测试数据输出一行一个整数表示按题目所述的固定冒泡排序过程将数组aaa排成非递减序列时所有实际发生交换的总代价之和。。样例1输入2 4 2 1 2 1 3 1 2 2 6 17 15 12 10 18 3 1 5 1 3 1 2输出1 7说明第一组数据中按标准冒泡排序过程恰好只会发生一次代价为111的交换因此答案为111。第二组数据中按照固定的冒泡排序顺序累计交换代价为777因此答案为777。思路和代码本题主要是利用冒泡排序的交换路径唯一性, 从前往后扫描排序和每次从当前最大值开始进行交换排序本质上是同一个过程只是观察角度不同。借助这个原理下面代码使用从当前最大值开始进行交换进行处理假设当前已排序好的元素数量为x, 当前未排序中最大值maxValue的处于数组中位置为pos, 那么本次maxValue的交换路径为pos - pos 1, pos 1 - pos 2.... , n-1-x-1 - n-1-x。求上述1过程中交换路径的代价可以采用前缀和进行加速求解。使用优先队列维护当前最大的元素值相同取位置更大的保证稳定性使用树状数组维护当前元素在“剩余数组”中的相对排名(求当前最大值)。整体流程重复执行以下操作取当前最大值用树状数组求它当前位置计算它经过的代价将其从树状数组和优先队列中删除。累加所有代价和就是结果算法时间复杂度为O(nlogn),空间复杂度为O(n)#includeiostream#includevector#includealgorithm#includefunctional#includequeueusingnamespacestd;usinglllonglong;constll INF1e18;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorlla(n1);for(inti1;in;i)cina[i];vectorllb(n1);for(inti1;in;i)cinb[i];// 边权 i交换是否计费vectorintc(n,0);// 边权前缀和vectorllpref_c(n,0);for(inti1;in;i){c[i](b[i]b[i1])?1:0;pref_c[i]pref_c[i-1]c[i];}// 最大值优先值相同位置大的优先priority_queuepairll,intpq;for(inti1;in;i){pq.push({a[i],i});}// 树状数组 维护当前元素相对位置vectorintfenw(n2,0);//autofenw_add[](intidx,intdelta){while(idxn){fenw[idx]delta;idxidx-idx;}};autofenw_sum[](intidx){intres0;while(idx0){resfenw[idx];idx-idx-idx;}returnres;};for(inti1;in;i)fenw_add(i,1);ll ans0;intcur_lenn;for(intstep0;stepn;step){auto[val,pos]pq.top();// 当前最大值及其原始位置pq.pop();intrankfenw_sum(pos);// 在当前未排序数组中的排名// 贡献从 rank 到 cur_len-1 的边权总和anspref_c[cur_len-1]-pref_c[rank-1];// 删除该元素fenw_add(pos,-1);--cur_len;}coutans\n;}return0;}