洛谷 P1908 逆序对 题解

时间：2023-12-22 23:33:50

每日一题 day43 打卡

Analysis

因为数据规模，所以我们需要对其进行离散化，新创一个数组a里面来放在我们的初始序列中在这个位置上的数是第几大的这里还要用一个小技巧排序，关于离散化的技巧我们具体在代码里面看

离散化之后我们只对a数组进行操作就好了，每次遇到一个数就把他插到树状数组里面去

双倍经验 洛谷 P1774 最接近神的人_NOI导刊2010提高（02）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define rep(i,s,e) for(register int i=s;i<=e;++i)

 #define dwn(i,s,e) for(fegister int i=s;i>+e;--i)

 #define maxn 5000000+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,ans;

 int a[maxn],re[maxn];

 int tree[maxn];

 inline int lowbit(int x)

 {

     return x&-x;

 }

 inline void build(int x,int k)

 {

     for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=k;

 }

 inline int ask(int x)

 {

     int res=;

     for(int i=x;i>=;i-=lowbit(i)) res+=tree[i];

     return res;

 }

 signed main()

 {

     n=read();

     rep(i,,n) a[i]=read(),re[i]=a[i];

     sort(a+,a+n+);

     int m=unique(a+,a+n+)-a-;

     rep(i,,n)

     {

         int now=lower_bound(a+,a+m+,re[i])-a;

         ans+=ask(m)-ask(now);

         build(now,);

     }

     write(ans);

     return ;

 }

请各位大佬斧正（反正我不认识斧正是什么意思）

相关文章