「杂烩」精灵魔法（P1908逆序对弱化版）
题面：
题目描述
(Tristan)解决了英灵殿的守卫安排后，便到达了静谧的精灵领地——(Alfheim) 。由于$ Midgard$ 处在$ Alfheim(和冥界) Hel$ 的中间，精灵族领地尚未受到冥界恶灵的侵入。族长$ Galanodel (为了帮助米德加尔特抵御外敌，对邪恶亡灵军团使用了高等魔法，从而使得亡灵军团每个士兵的行进速度变得不一致，从而打乱冥王)Hel$安排的最佳阵型。
由于这个军团离(Midgard)还很远，因此在抵达$ Midgard$ 之前，对于$ A,B$ 两个亡灵，若$A (的初始位置在) B(后面且)A (的速度比 快，)A (就会冲到)B (的前面去。现在)Galanodel$ 想知道，会有多少对亡灵之间出现反超现象？
输入格式
第一行一个整数$ n$，表示排成一队的邪恶亡灵军团有多少人。
第二行(n)个整数(a[i])，表示邪恶亡灵们在数轴上的初始坐标。数据保证这些坐标全部不同。亡灵军团向数轴正方向前进。
第三行(n)个整数 (v[i])，表示邪恶亡灵们的行进速度。
输出格式
一行一个正整数(k)，表示「反超」的个数。
样例
样例输入
3
1 2 3
2 1 3
样例输出
1
数据范围与提示
$ n<= 100000$
所有数据的绝对值均不超过(maxlongint)。
解法一：朴素的暴力（50pts）
一看就让我们求排序后的逆序对，(O(n^2))搞它
代码：
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
typedef long long ll;
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n;
ll ans,minn,maxx;
struct Node{
ll d,v;
}a[maxn];
bool cmp(Node A,Node B){return A.d<B.d;}
int main(){
//freopen("a.in","r",stdin);
n=read();
for(int i=1;i<=n;i++)cin>>a[i].d;
for(int i=1;i<=n;i++)cin>>a[i].v;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].v>a[j].v)ans++;
}
}
cout<<ans;
return 0;
}
解法2：智障的set（40pts）
先介绍个函数：(algorithm)库里的(distance)函数能够轻易的帮我们把迭代器转成下标处理，用到set上就十分合适
利用set自动排序的功能，可以轻易处理逆序对，将位置从大到小(sort)一遍，找新序列的正序对就行了（正序是逆序对，倒序不就是正序对么）
如果新元素比队尾元素大，说明前面所有元素都能于它构成正序对，相反，就可以利用(lowerbound)函数找到第一个大于等于它的位置，恰好是它能组成的正序对个数
但是由于set时间效率极低，还没暴力跑的快，用这个练习练习STL就行了
代码：
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
typedef long long ll;
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,f[maxn];
ll ans;
struct Node{
ll d,v;
}a[maxn];
multiset<int> s;
bool cmp(Node A,Node B){return A.d>B.d;}
int main(){
// freopen("a.in","r",stdin);
n=read();
for(int i=0;i<n;i++)cin>>a[i].d;
for(int i=0;i<n;i++)cin>>a[i].v;
sort(a,a+n,cmp);
s.insert(a[0].v);
f[0]=0;
for(int i=1;i<n;i++){
int len=s.size();
if(a[i].v>=*s.rbegin()){//注意，set的end()是假的，只能这样求队尾元素
f[i]=len,s.insert(a[i].v);
}else{
// cout<<(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v)<<endl;
f[i]=distance(s.begin(),s.lower_bound(a[i].v));//distance将迭代器转下标
s.insert(a[i].v);
}
//for(int i=0;i<n;i++)cout<<ve[i]<<" ";
//cout<<endl;
}
for(int i=0;i<n;i++)ans+=f[i];
cout<<ans;
return 0;
}
解法3：vector模拟set（100pts）
众所周知，(vector)功能强大，轻易就能排个序，效率比set还高不少，但是终究过不了加强版的P1908
代码：
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
typedef long long ll;
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,f[maxn];
ll ans;
struct Node{
ll d,v;
}a[maxn];
vector<int> ve;
bool cmp(Node A,Node B){return A.d>B.d;}
int main(){
// freopen("a.in","r",stdin);
n=read();
for(int i=0;i<n;i++)cin>>a[i].d;
for(int i=0;i<n;i++)cin>>a[i].v;//狗比vector只能从0开始存
sort(a,a+n,cmp);
ve.push_back(a[0].v);
f[0]=0;
for(int i=1;i<n;i++){
int len=ve.size();
if(a[i].v>=ve.back()){
f[i]=len,ve.push_back(a[i].v);
}else{
// cout<<(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v)<<endl;
f[i]=lower_bound(ve.begin(),ve.end(),a[i].v)-ve.begin();//注意写法，考试就在这被卡住了
ve.insert(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v);//假装排序
}
//for(int i=0;i<n;i++)cout<<ve[i]<<" ";
//cout<<endl;
}
for(int i=0;i<n;i++)ans+=f[i];
cout<<ans;
return 0;
}
解法4：树状数组（100pts）
对结构体(a[i])排序，按位置从小到大的顺序排，利用辅助数组b记录排序后的位置，将位置插入树状数组，咨询一下后缀和即可
代码：
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
typedef long long ll;
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,f[maxn];
ll ans,b[maxn],c[maxn];
struct Node{
ll d,v;
}a[maxn];
bool cmp(Node A,Node B){return A.d<B.d;}
ll Lowbit(ll x){return x&-x;}
void update(ll x){
while(x<=n){
c[x]++;
x+=Lowbit(x);
}
}
ll query(ll x){
ll sum=0;
while(x){
sum+=c[x];
x-=Lowbit(x);
}
return sum;
}
int main(){
//freopen("a.in","r",stdin);
n=read();
for(int i=1;i<=n;i++)cin>>a[i].d;
for(int i=1;i<=n;i++)cin>>a[i].v,b[i]=a[i].v;
sort(a+1,a+n+1,cmp);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)a[i].v=lower_bound(b+1,b+1+n,a[i].v)-b;
for(int i=n;i>=1;i--){
ans+=query(a[i].v-1);update(a[i].v);
}
cout<<ans;
return 0;
}
解法5：归并排序（100pts）
这就不用写了吧，归并能处理逆序对（貌似也只有这个用途）