求逆序对数（卡常)洛谷1908

至今没有遇到过卡常的题，今天可算是遇到了
洛谷P1908求逆序对数
题解：

就是一道求简单的逆序对数，但是最重要的一点是求逆序对数并不需要离散化去重，但平常我写离散化写太多了，就一般会去重，而且对卡常的题，我就把输入模板换成了更快的read(）

AC代码：

#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1e6+5;
ll c[maxn],n,num[maxn];
vector<ll>vec;
template<class T>inline void read(T &res)
{
    char c;
    T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';
    res*=flag;
}
ll getid(ll x)
{
    return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
}
ll lowbit(ll x)
{
    return x&(-x);
}
void update(ll i,ll k)
{
    while(i<=n)
    {
        c[i]+=k;
        i+=lowbit(i);
    }
}
ll getsum(ll k)
{
    ll res=0;
    while(k>0)
    {
        res+=c[k];
        k-=lowbit(k);
    }
    return res;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
    {
        ll x;
        read(num[i]);
        vec.push_back(num[i]);
    }
    sort(vec.begin(),vec.end());
    ll res=0;
    for(ll i=1; i<=n; i++)
    {
        update(getid(num[i]),1);
        res+=getsum(n)-getsum(getid(num[i]));
    }
    printf("%lldn",res);

}

最后

以上就是无语导师为你收集整理的求逆序对数（卡常)洛谷1908的全部内容，希望文章能够帮你解决求逆序对数（卡常)洛谷1908所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。