教做潮男的网站,岳阳seo优化,南山做网站,深圳建设工程质量协会网站简介 首先解释一下什么是逆序数#xff0c;在一个排列中#xff0c;如果前面的数大于后面的数#xff0c;则称这两个数为一对逆序#xff0c;而在这个排列中逆序对的总数称为逆序数。 然后对于树状数组#xff0c;如果有一点了解的话#xff0c;树状数组一般是用于数组区…简介 首先解释一下什么是逆序数在一个排列中如果前面的数大于后面的数则称这两个数为一对逆序而在这个排列中逆序对的总数称为逆序数。 然后对于树状数组如果有一点了解的话树状数组一般是用于数组区间求和加单点修改的一种数据结构。如果不了解可以去百度一下。 思路 我们要求逆序数不能直接针对这个排列进行树状数组的添加和求和这样也没有意义。 我们需要对于排列中的每一个数是否出现进行树状数组的操作。用一个数组visvis[i]1表示i在这个排列中为0就表示不存在。 那我们遍历一遍排列对于出现的每一个数我们进行树状数组的添加加一。表示这个数出现在排列中了。而如果求和的操作即表示求在当前位置之前比这个数小的数目。 那i-suma即表示大于这个数的数目i是当前数的位置a表示这个数。 代码 #include bits/stdc.h
using namespace std;
int num[100005];
int n100005;
int lowbit(int i){return i-i;
}
void add(int x,int y){for(int ix;in;ilowbit(i)){num[i]y;}
}
int sum(int x){int ans0;while(x0){ansnum[x];x-lowbit(x);}return ans;
}
int main()
{int m;while(cinm){int a;long long ans0;for(int i1;im;i){cina;add(a,1);ansi-sum(a);}coutansendl;}return 0;
} 题目来源https://ac.nowcoder.com/acm/problem/15163转载于:https://www.cnblogs.com/maybe96/p/10300330.html
