题解 P1908 【逆序对】

渡海 · 2017-09-09 16:15:05 · 题解

蒟蒻表示，这道题很有意思..会树状数组的用树状数组，会线段树的用线段树，我都不会，用Upper_bound

核心代码两行。

Code：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> shu;
int main(){
    scanf("%d",&n);    
    long long s=0,a;
    int kk[60000];
    for(int i=0;i<n;i++){
        scanf("%d",&kk[i]);//核心代码：
        s+=shu.end()-upper_bound(shu.begin(),shu.end(),kk[i]);
        shu.insert(upper_bound(shu.begin(),shu.end(),kk[i]),kk[i]);
    }
    printf("%d",s);
    return 0;
}
看着楼下一堆堆长长的代码就头疼233