求逆序对

　　题目大意：给你一个序列，求逆序对个数。

　　注释：n<=$10^5$。

　　　　此题显然可以跑暴力。想枚举1到n，再求在i的后缀中有多少比i小的，统计答案即可。这显然是$n^2$的。这...显然过不去，我们思考如何优化？显然，这里的有些过程是重复的。我们将这个序列设为a序列，对于两个1到n中的整数i<j，在j后面的数我们进行了多次重复枚举，我们思考如何优化。容易想到用一个桶来记录。只需要记录对于每一个数来讲，我后面有多少个数是比我小的，只需要将桶中的数累加即可。但是，我们必须记录是这个数之后的桶的含义，也就是说这个数之前的桶我们不可以进行修改，所以我们必须逆向枚举，这时一种做法，但是我们这里讲另一种做法：正向枚举。我们只需要记录这个数之前的桶的状况即可，查询时，只需要记录当前桶的前缀和，但是，我们如何修改这个前缀和？如果用数组实现的话修改是O(n)的，所以这个时间复杂度还是$n^2$的。而这个过程我们可以用树状数组维护。树状数组是针对桶的，也就是说，我树状数组记录的也是区间和，只不过这个区间和是针对桶的。我们在修改的时候只需要对于前面的，所有能看见这个数的树状数组进行修改。每个树状数组的节点的视野就是它后面的数。在查询时，我们只需要查询在这个数视野之内的数。显然，我们对于视野的理解是贪心的，即，这个数只能看见比自己大的数的桶。

　　最后，附上丑陋的代码......

 #include <iostream>

 #include <cstdio>

 #define N 100010

 using namespace std;

 typedef long long ll;

 int n,a[N],sum[N];

 ll ans;

 inline void fix(int x)

 {

     while(x)sum[x]++,x-=x&(-x);

 }

 inline int getsum(int x)

 {

     int re=;

     while(x<=)re+=sum[x],x+=x&(-x);

     return re;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     for(int i=;i<=n;i++)

     {

         ans+=getsum(a[i]+);

         fix(a[i]);

     }

     printf("%lld",ans);

     return ;

 }

　　真难理解啊，博主智商低啊！！

巴特西

求逆序对[树状数组] jdoj

求逆序对

最新文章

热门文章