「杂烩」精灵魔法（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）
这就不用写了吧，归并能处理逆序对（貌似也只有这个用途）