【题解】P1908 -归并排序求逆序对和

2018-10-22 21:26:32

#### 接下来就是我们解题的步骤了:

io模板详解链接：https://twi.blog.luogu.org/duliu-io

#include<cstdio>
using namespace std;
#define ll long long

namespace io {  //io模板详见个人博客
#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
const int SIZ = 1 << 21 | 1;
char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;
int fr;
inline void out() {
fwrite(obuff, 1, oS - obuff, stdout);
oS = obuff;
}
template<class Type>
x = 0;
Type y = 1;
for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());
c == '-' ? y = -1 : x = (c & 15);
for (c = gc(); c >= '0' && c <= '9'; c = gc())
x = x * 10 + (c & 15);
x *= y;
}
template<class Type>
inline void print(Type x, char text = '\n') {
if (x < 0)
*oS++ = '-', x *= -1;
if (x == 0)
*oS++ = '0';
while (x)
fu[++fr] = x % 10 + '0', x /= 10;
while (fr)
*oS++ = fu[fr--];
*oS++ = text;
out();
}
}
using namespace io;  //以上为玄(du)学(liu)优(ka)化(chang)

ll ans[500010], mem[500010], anss;
int n;

void merge(int lo, int mid, int hi) {
int i = lo, e = mid + 1, k = lo;
while (i <= mid && e <= hi) {
if (ans[i] <= ans[e])
mem[k++] = ans[i++];
else
anss += e - k, mem[k++] = ans[e++]; //求逆序对和
}
while (i <= mid)
mem[k++] = ans[i++];
while (e <= hi)
mem[k++] = ans[e++];
for (i = lo; i <= hi; ++i)
ans[i] = mem[i];
}

void merge_sort(int x, int y) {
if (x < y) {
int mid = (x + y) / 2;
merge_sort(x, mid);
merge_sort(mid + 1, y);
merge(x, mid, y);
}
}

int main() {
for (register int i = 0; i < n; ++i)
}