HDU 4911 Inversion 树状数组求逆序数对

显然每次交换都能降低1

所以求出逆序数对数，然后-=k就好了。。

。

_(:зゝ∠)_ 

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<set> #include<map> #include<iostream> #include<algorithm> using namespace std; #define N 100005 #define ll long long ll c[N+100000], maxn; inline ll Lowbit(ll x){return x&(-x);} void change(ll i, ll x)//i点增量为x { while(i <= maxn) { c[i] += x; i += Lowbit(i); } } ll sum(ll x){//区间求和 [1,x] ll ans = 0; for(ll i = x; i >= 1; i -= Lowbit(i)) ans += c[i]; return ans; } ll a[N], n, k; set<ll>s; set<ll>::iterator p; map<ll,ll>mp; int main(){ll i;while(cin>>n>>k){s.clear(); mp.clear();for(i = 1; i <= n; i++)scanf("%I64d",&a[i]), s.insert(a[i]);maxn = n+100;for(p = s.begin(), i = 2; p!=s.end(); p++, i++){mp[*p] = i;}for(i = 1; i <= n; i++)a[i] = mp[a[i]];memset(c, 0, sizeof c);ll ans = 0;for(i = n; i >= 1; i--){ans += sum(a[i]-1);change(a[i], 1);}ans -= k;cout<< max(0ll, ans) <<endl;}return 0; }

总结

以上是生活随笔为你收集整理的HDU 4911 Inversion 树状数组求逆序数对的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。