题目链接:https://vjudge.net/contest/358908#problem/H
题目大意:给你一个序列,问你这个序列经过冒泡排序形成的非递减序列所需要的次数
很经典的线段树求逆序数的题,对于序列中的一个数字来说,把他移动到在非递减序列中的位置的交换次数就是他前面
比他大的数字的数目,至于每次交换的后续性这是不用考虑的,因为这里只是说相对位置
#include<set> #include<map> #include<stack> #include<queue> #include<cmath> #include<cstdio> #include<cctype> #include<string> #include<vector> #include<climits> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define endl '\n' #define rtl rt<<1 #define rtr rt<<1|1 #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define maxx(a, b) (a > b ? a : b) #define minn(a, b) (a < b ? a : b) #define zero(a) memset(a, 0, sizeof(a)) #define INF(a) memset(a, 0x3f, sizeof(a)) #define IOS ios::sync_with_stdio(false) #define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n") using namespace std; typedef long long ll; typedef pair<int, int> P; typedef pair<ll, ll> P2; const double pi = acos(-1.0); const double eps = 1e-7; const ll MOD = 1000000007LL; const int INF = 0x3f3f3f3f; const int _NAN = -0x3f3f3f3f; const double EULC = 0.5772156649015328; const int NIL = -1; template<typename T> void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } const int maxn = 1e6+10; int arr[maxn], t[maxn], tree[maxn<<2]; void build(int rt, int l, int r) { tree[rt] = 0; if (l==r) return; int mid = (l+r)>>1; build(lson); build(rson); } void change(int pos, int rt, int l, int r) { if (l==r) { tree[rt] |= 1; return; } int mid = (l+r)>>1; pos <= mid ? change(pos, lson) : change(pos, rson); tree[rt] = tree[rtl] + tree[rtr]; } ll find(int st, int ed, int rt, int l, int r) { if (st<=l && ed>=r) return tree[rt]; int mid = (l+r)>>1; ll ans = 0; if (st<=mid) ans += find(st, ed, lson); if (ed>mid) ans += find(st, ed, rson); return ans; } int main(void) { int n; while(~scanf("%d", &n) && n) { for (int i = 1; i<=n; ++i) { scanf("%d", &arr[i]); t[i] = arr[i]; } sort(t+1, t+n+1); int last = unique(t+1, t+n+1)-t; for (int i = 1; i<=n; ++i) arr[i] = lower_bound(t+1, t+last, arr[i])-t; ll sum = 0; for (int i = 1; i<=n; ++i) { sum += find(arr[i], last, 1, 1, last); change(arr[i], 1, 1, last); } printf("%lld\n", sum); build(1, 1, last); } return 0; }