学步园

求逆序对的题目，可以用暴力、树状数组来实现。

1。暴力法：O(n^2)对于1000的规模完全可以做，直接找第i个元素之后有多少个比其小的元素即可。

代码：

#include <iostream><br /> #include <cstdio><br /> #include <cstring><br /> #include <cstdlib></p> <p>using namespace std;</p> <p>int main()<br /> {<br /> int t,n,cnt=0;<br /> int a[1005];<br /> int ret;</p> <p> scanf("%d",&t);<br /> while(t--)<br /> {<br /> cnt++;<br /> scanf("%d",&n);<br /> for(int i=0;i<n;i++)<br /> scanf("%d",&a[i]);</p> <p> ret=0;<br /> for(int i=0;i<n;i++)<br /> for(int j=i+1;j<n;j++)<br /> if(a[i]>a[j])<br /> ret++;<br /> printf("Scenario #%d:/n",cnt);<br /> printf("%d/n",ret);<br /> if(t)<br /> printf("/n");<br /> }</p> <p> return 0;<br /> }<br />

运用树状数组，每次维护小于K的数的个数，从后往前求和，时间复杂度是O(nlogn)的，注意数的范围很大，是2000000，这样用这种方法反而不快。

代码：

#include <iostream><br /> #include <cstdio><br /> #include <cstring><br /> #include <cstdlib></p> <p>using namespace std;</p> <p>const int MAX=2000100;<br /> int seg[MAX],a[1100];</p> <p>void add(int k)<br /> {<br /> while(k<MAX)<br /> {<br /> seg[k]++;<br /> k+=k&-k;<br /> }<br /> }</p> <p>int sum(int k)<br /> {<br /> int ret=0;</p> <p> while(k)<br /> {<br /> ret+=seg[k];<br /> k-=k&-k;<br /> }</p> <p> return ret;<br /> }</p> <p>int main()<br /> {<br /> int t,n,cnt=0;<br /> int ret;</p> <p> scanf("%d",&t);<br /> while(t--)<br /> {<br /> cnt++;<br /> scanf("%d",&n);<br /> for(int i=0;i<n;i++)<br /> {<br /> scanf("%d",&a[i]);<br /> a[i]+=1000001;<br /> }</p> <p> ret=0;<br /> memset(seg,0,sizeof(seg));<br /> for(int i=n-1;i>=0;i--)<br /> {<br /> ret+=sum(a[i]-1);<br /> add(a[i]);<br /> }<br /> printf("Scenario #%d:/n",cnt);<br /> printf("%d/n",ret);<br /> if(t)<br /> printf("/n");<br /> }</p> <p> return 0;<br /> }<br />

我也尝试写了一下，但是超时了，由于数的范围大，而线段树的初始化时间效率低，线段树的初始化时间是O(nlogn)而树状数组的初始化时间是O(n)的，这里差距很大。

总结：能用树状数组代替线段树的，尽量代替，不仅代码量小，而且效率高。