威风镰鼬

分类

题解(153)

/ 注册

全部文章（共3篇）

题解 | #[NOIP2013]火柴排队#

思路稍微用点群论的知识，我们可以感觉出它要我们求逆序对。于是我们可以先把a和b的数字和离散化结果记录下来，然后用x存储置换后的结果，然后套个归并排序的板子就OK啦。代码 #include<bits/stdc++.h> using namespace std; const int ma...

离散化归并排序 NOIP

2021-08-18

1 464

题解 | #珂朵莉的数列#

思路可以顺便把这道一模一样的题给A掉Luogu P5463 小鱼比可爱（加强版）各位可以做完《逆序数》再过来，我是用归并排序写的。考虑到对于一个逆序对<i,j>，i∈[l,m],j∈[m+1,r]，那么它是所有区间[x,y]，x∈[l,i]，y∈[j,r]中的逆序对，每一次merge计...

树状数组归并排序离散化

2021-06-15

1 555

题解 | #逆序数#

思路先看一眼数据范围，1e5逐个数逆序数是肯定会超时的；对于排序后的数组，每一个数前面序号比它大的数的个数就是它的逆序数，因此我们可以想到一种O(nlogn)排序并求逆序数的方法，只需要套一个归并排序的板子，然后统计归并排序时每个区域交换元素时相隔的元素个数就好了。代码 #include<...

排序归并排序逆序对

2021-06-12

1 564