保定 网站,新媒体网络营销的概念,在线设计网站海报,万网个人网站怎么备案蓝桥集训之火柴排队 核心思想#xff1a;离散化归并排序 由于数据范围较小10w 需要控制时间复杂度到nlogn 同时排两个数组会超时所以将a数组离散化成顺序数组 b数组离散化后再归并排序求逆序对数量 #includeiostream#include algorithm#include cstrin…蓝桥集训之火柴排队 核心思想离散化归并排序 由于数据范围较小10w 需要控制时间复杂度到nlogn 同时排两个数组会超时所以将a数组离散化成顺序数组 b数组离散化后再归并排序求逆序对数量 #includeiostream#include algorithm#include cstringusing namespace std;const int N 100010 , MOD 99999997;int n;int a[N],b[N],p[N],c[N];int find(int x) //离散化二分{int l1,rn;while(lr){int mid lr 1;if(p[mid] x ) r mid;else l mid 1;}return l;}void work(int a[]) //离散化{for(int i1;in;i) p[i] a[i]; //将原本的a数组存下 仅用于排序sort(p1,pn1);for(int i1;in;i) a[i] find(a[i]); //更新a数组元素为应该在的下标(根据元素大小)}int merge_sort(int l,int r) //求逆序对数量{if(lr) return 0;int mid lr 1;int res (merge_sort(l,mid) merge_sort(mid1,r));int i l,j mid 1,k0;while(imid jr){if(b[i] b[j]) p[k] b[i];else p[k] b[j] , res (res mid - i 1) % MOD;}while(imid) p[k] b[i];while(jr) p[k] b[j];for(int il,j0;ir;i,j) b[i] p[j];return res;}int main(){cinn;for (int i 1; i n; i ) scanf(%d, a[i]);for (int i 1; i n; i ) scanf(%d, b[i]);work(a),work(b);for(int i1;in;i) c[a[i]] i; //c数组用来保存 对应关系for(int i1;in;i) b[i] c[b[i]]; //b数组按照 对应关系 更新coutmerge_sort(1,n); //b数组归并return 0;}
