例题一：逆序对的数量
传送门
题意
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第i 个和第个元素，如果满足ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含n个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1<=n<=10^5
数列中的元素的取值范围[1,10^9]
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路
或者：
for (int i = 1; i <= n; i++) { res += i - 1 - sum(rk[i]); add(rk[i], 1); }
for (int i = 1; i <= n; i++) { add(rk[i], 1); res += i - sum(rk[i]); }
代码
对了，记得开long long
- 归并排序
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 100010; int n; int a[N], tmp[N]; ll merge_sort(int l, int r) { if(l >= r) return 0; ll mid = (l + r) >> 1; ll res = merge_sort(l, mid) + merge_sort(mid + 1, r); int k = 0, i = l, j = mid + 1; while(i <= mid && j <= r) { if(a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; res += mid - i + 1; } } while(i <= mid) tmp[k++] = a[i++]; while(j <= r) tmp[k++] = a[j++]; for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j]; return res; } int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> a[i]; cout << merge_sort(0, n - 1) << endl; return 0; }
- 树状数组 + 离散化
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; const int N = 500010; int n; int rk[N]; int tr[N]; struct node { int val, id; bool operator<(const node &t) const { if(val == t.val) { return id < t.id; } return val < t.val; } }a[N]; int lowbit(int x){ return x & -x ; } int sum(int x){ long long res = 0 ; for(int i = x ; i ; i -= lowbit(i)) res += tr[i] ; return res; } void add(int x , int c){ for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c ; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].val; a[i].id = i; } sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { rk[a[i].id] = i; } ll res = 0; for (int i = 1; i <= n; i++) { add(rk[i], 1); res += i - sum(rk[i]); } cout << res << endl; return 0; }
- 树状数组 + 离散化
#include <iostream> #include <cstring> #include <algorithm> #include <bits/stdc++.h> using namespace std; const int N = 100010; int n; int tr[N], a[N]; vector<int> id; void add(int x, int c) { for (; x <= N; x += x & -x) tr[x] += c; } long long sum(int x) { long long res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } int find(int x) { int l = 0, r = id.size() - 1; while(l < r) { int mid = l + r >> 1; if(id[mid] >= x) r = mid; else l = mid + 1; } return l + 1; } int main() { cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i], id.push_back(a[i]); sort(id.begin(), id.end()); id.erase(unique(id.begin(), id.end()), id.end()); long long res = 0; for (int i = 1; i <= n; i++) { int y = find(a[i]); add(y, 1); res += sum(n) - sum(y); } cout << res << endl; return 0; }
例题二：Minimum Inversion Number
题意
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
思路
题意： 数组 a是 0 ~ n-1 的全排列，询问逆序对个数的最小值。给定一个序列，每次把序列的第一个数移动到最后，求每次操作后新序列的逆序对个数的最小值。
首先元素的数据范围不大，不必离散化，直接开权值线段树，结点维护元素的个数。离线，每次输入一个数，查询操作求出比其大的数字的个数，然后做单点更新。
再 for 一遍序列，每次把元素 a[i] 移动到最后，新增的答案贡献等于ans 先减去比a[i] 小的元素（因为把 a[i] 要放置最后），再加上比 a[i] 大的元素，这样更新下去,取 min 即可。
代码
权值线段树
// #include <bits/stdc++.h> #include <iostream> #include <algorithm> using namespace std; #define ls u<<1 #define rs u<<1|1 const int N = 5010; struct node { int l, r; int sum; } tr[N << 2]; int n, a[N]; void pushup(int u) { tr[u].sum = tr[ls].sum + tr[rs].sum; } void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) return ; int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int x) { if(tr[u].l >= x && tr[u].r <= x) { tr[u].sum = 1; return ; } int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(ls, x); else modify(rs, x); pushup(u); } int query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } int mid = tr[u].l + tr[u].r >> 1; int res = 0; if(l <= mid) res = query(ls, l, r); if(r > mid) res += query(rs, l, r); return res; } // http://acm.hdu.edu.cn/showproblem.php?pid=1394 int main() { while(cin >> n) { for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); int ans = 0x7fffffff, res = 0; for (int i = 1; i <= n; i++) { res += query(1, a[i] + 1, n); modify(1, a[i] + 1); } ans = min(res, ans); for (int i = 1; i <= n; i++) { res = res + (-a[i] + n - a[i] - 1); ans = min(ans, res); } cout << ans << endl; } return 0; }
- 当然树状数组也是可以的。
// #include<bits/stdc++.h> #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N = 5010; int n; int rk[N], tr[N]; struct node { int val, id; bool operator<(const node &A) const { return val < A.val; } }a[N]; int lowbit(int x){ return x & -x ; } int sum(int x){ int res = 0 ; for(int i = x ; i ; i -= lowbit(i)) res += tr[i] ; return res; } void add(int x , int c){ for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c ; } signed main() { while(cin >> n) { memset(tr, 0, sizeof tr); for (int i = 1; i <= n; i++) { cin >> a[i].val; a[i].id = i; } sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { rk[a[i].id] = i; } int ans = 2e17, res = 0; for (int i = 1; i <= n; i++) { add(rk[i], 1); res += i - sum(rk[i]); } ans = min(res, ans); for (int i = 1; i <= n; i++) { res = res + (-a[rk[i]].val + n - a[rk[i]].val - 1); ans = min(ans, res); } cout << ans << endl; } return 0; }
- 动态开点线段树
// #include <bits/stdc++.h> #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N = 5010; struct node { int l, r; int sum; } tr[N]; // 修改n次，加上n个点 int n, root, idx, a[N]; void pushup(int p) { tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum; } void modify(int &p, int l, int r, int x, int v) { if(!p) p = ++idx; if(l >= x && r <= x) { tr[p].sum = v; return ; } int mid = l + r >> 1; if(x <= mid) modify(tr[p].l, l, mid, x, v); else modify(tr[p].r, mid + 1, r, x, v); pushup(p); } int query(int p, int l, int r, int ql, int qr) { if(!p) return 0; if(l >= ql && r <= qr) return tr[p].sum; int mid = l + r >> 1; int v = 0; if(ql <= mid) v = query(tr[p].l, l, mid, ql, qr); if(qr > mid) v += query(tr[p].r, mid + 1, r, ql, qr); return v; } signed main() { while(cin >> n) { memset(tr, 0, sizeof tr); root = idx = 0; int ans = 2e17, res = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; res += query(root, 1, n, a[i] + 1, n); modify(root, 1, n, a[i] + 1, 1); } ans = min(res, ans); for (int i = 1; i <= n; i++) { res = res + (-a[i] + n - a[i] - 1); ans = min(ans, res); } cout << ans << endl; } return 0; }
