很难受，看了这么长时间才看明白，我好笨，这里的“顺序数”一直弄不明白为什么这么写就能算出来出来，原来是，按照开始输入的顺序遍历，把每个i的最终位置处标记，只要在这个i前面并且比他小，那么求前i项和就能取到，也就是到i为止，他前面最终位置比他小的有几个，就是顺序数
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=500000+10; struct note { int x,id; bool operator <(const note &p) { return x<p.x; } } a[maxn]; int s[maxn],t[maxn]; int n; void add(int x,int v) { for(int i=x; i<=n; i+=i&-i) s[i]+=v; } int sum(int x) { int sum=0; for(int i=x; i>0; i-=i&-i) sum+=s[i]; return sum; } int main() { while(~scanf("%d",&n)&&n) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); a[i].id=i; } memset(s,0,sizeof(s)); sort(a+1,a+n+1); for(int i=1; i<=n; i++) { t[a[i].id]=i; } long long int ans=0; for(int i=1; i<=n; i++) { add(t[i],1); ans+=i-sum(t[i]);//位置减去顺序数就是逆序数 } printf("%lld\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7267178.html
