nyoj-117（離散化）

#include<stdio.h> #include<string.h> #include<algorithm> 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<p.v;return q.w<p.w; } int lowbit(int x) {return x&(-x); } int sum(int pos) {int res=0;while(pos>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<stdio.h> #include<string.h> #include<algorithm> 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);} }

總結(jié)

以上是生活随笔為你收集整理的nyoj- 117 求逆序数 hdu-sort it---- 树状数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。