/*
luogu P1966 火柴排队
神TM逆序对。。。
noip怎么这么坑啊。。
暴力都没得打
此题模拟考试时爆了0
做法
将A数组排序,由于B数组与A数组是一一对应的
那么B数组的位置也会发生相应的变化
此时B数组逆序数对数即为答案
*/
#include < cstdio > #include < iostream > #include < algorithm >
const int BUF = 123123123;
char Buf[BUF],
*buf = Buf;
inline void read(int & now) {
for (now = 0; ! isdigit( * buf); ++buf);
for (; isdigit( * buf); now = now * 10 + *buf - ‘0‘, ++buf);
}#define Mod 99999997#define Max 1232334
struct Data {
int x,
Id;
bool operator < (const Data & now) const {
return this - >x < now.x;
}
};
Data a[Max],
b[Max];
int key[Max];
struct Bit_Tree {
protected: int data[Max],
N;
public: inline void Prepare(int x) {
this - >N = x;
}
void C(int pos) {
for (; pos <= N; pos += pos & -pos)++data[pos];
}
int Q(int pos) {
register int i;
int res = 0;
for (i = N; i; i -= i & -i) res += data[i];
for (i = pos - 1; i; i -= i & -i) res -= data[i];
return res;
}
};
Bit_Tree Bit;
int Main() {
freopen("match.in", "r", stdin);
freopen("match.ans", "w", stdout);
fread(buf, 1, BUF, stdin);
int N;
read(N);
register int i;
int Answer = 0;
for (i = 1; i <= N; ++i) read(a[i].x),
a[i].Id = i;
for (i = 1; i <= N; ++i) read(b[i].x),
b[i].Id = i;
std: :sort(a + 1, a + 1 + N);
std: :sort(b + 1, b + 1 + N);
for (i = 1; i <= N; ++i) key[a[i].Id] = b[i].Id;
for (i = 1, Bit.Prepare(N); i <= N; ++i) {
Bit.C(key[i]);
Answer = (Answer + Bit.Q(key[i] + 1)) % Mod;
}
printf("%d", Answer);
return 0;
}
int ZlycerQan = Main();
int main(int argc, char * argv[]) {;
}
来源: http://www.bubuko.com/infodetail-2273948.html