本文共 1426 字，大约阅读时间需要 4 分钟。
nyoj-117（离散化）
#include #include #include using namespace std;long long a[1000009];int n;struct ni{ int v,w;}b[1000009];int cmp(ni q,ni p){ if(q.v!=p.v) return q.v 0) { res+=a[pos]; pos-=lowbit(pos); } return res;}void plus(int pos){ while(pos<=n) { a[pos]++; pos+=lowbit(pos); }}int main(){ int m,i; scanf("%d",&m); while(m--) { memset(a,0,sizeof(a)); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&b[i].v); b[i].w=i; } sort(b+1,b+n+1,cmp); long long k=0; for(i=1;i<=n;i++) { plus(b[i].w); k+=i-sum(b[i].w); } printf("%lld\n",k); }}
hdu-sort it
#include #include #include using namespace std;int a[1005];int n;int lowbit(int x){ return x&(-x);}void add(int pos,int num){ while(pos <= n) { a[pos] += num; pos += lowbit(pos); }}int Get_sum(int pos){ int res = 0; while(pos > 0) { res += a[pos]; pos -= lowbit(pos); } return res;}int main(){ int x; while(~scanf("%d",&n)) { memset(a,0,sizeof(a)); int sum = 0; for(int i = 1; i <= n; i++) { scanf("%d",&x); add(x,1); sum += i - Get_sum(x); } printf("%d\n",sum); }}
转载地址：http://xysgi.baihongyu.com/