使用基于策略的数据结构进行反转计数
我们将使用 g++ 头文件在 C++ 编译器中编译代码。g++ 是一个基于 Linux 的头文件，用于在 C++ 中编译基于策略的数据结构的代码。基于策略的数据结构是为了提高代码的性能和灵活性而使用的。由于这些数据结构资源丰富，我们可以用它们实现许多功能，例如查找元素的索引、将元素插入到索引位置、从索引范围中移除元素等等。
示例
我们以反转计数为例 -
假设构造的树的内部遍历为 1,2,3,4,5，当我们遍历反转它时，树的形式变为 5,4,3,2,1。
我们以以下树结构作为输入
< 5, 4, 3, 2, 1 >
给定的树结构长度为 4。现在我们将考虑以下步骤来理解反转的过程。
步骤 1 − 元素从 index[0] 开始，即 5，并与每个元素配对，直到 index[4]，即 1。因此，索引 0 到 4 之间的总数为 4。
(5…4), (5…3), (5…2), (5…1)
步骤 2 − 元素从 index[1] 开始，即 4，并与每个元素配对，直到 index[4]，即 1。因此，索引 1 到 4 之间的总数为 3。
(4…3), (4…2), (4…1)
步骤 3 − 元素从 index[2] 即 3 开始，并与每个元素配对，直到 index[4] 即 1。因此，索引 2 到 4 之间的总数为 2。
(3…2), (3…1)
步骤 4 − 元素从 index[3] 即 2 开始，并与每个元素配对，直到 index[4] 即 1。因此，索引 3 到 4 之间的总数为 1
(2…1)
这样，我们可以写出给定构造树的反转。因此，count(4+3+2+1) 的反转总数为10
在本文中，我们将使用基于策略的数据结构来解决反转计数问题。
语法
程序中使用了以下语法 -
vector <data_type> vector_variable_name
参数
data_type − 用于向量的数据类型。
vector_variable_name − 用于向量的变量名称。
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
参数
typedef − 这是 C++ 程序中使用的保留关键字。
int − 用于插入数组项的数据类型。
null_type − 这是一个映射策略，以集合形式使用。如果我们想要映射，那么第二个参数必须是映射类型。
less<int> − 两个函数之间的比较。
rb_tree_tag − 用于插入和删除的红黑树的类型。
tree_order_statistics_node_update − 这基于头文件"tree_policy.hpp"，其中包含基于树的容器更新节点变体的各种操作。因此，我们将继续跟踪子树中的节点。
pbds − 基于策略数据结构的变量名称。
order_of_key()
算法
我们将使用头文件 iostream 和 vector 启动程序。然后，我们将提到基于策略数据结构 (pbds) 的 g++ 头文件。
我们将使用基于策略数据结构 (pbds) 的 GNU 必要命名空间，即 "using namespace __gnu_pbds"。 它将初始化基于 pbds 的树格式，即 "typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 使用这些函数，我们将跟踪子树中的节点。
我们定义了一个双精度长整型函数'inversion_Cnt'，它接受向量整型参数并存储数组元素的地址。
我们将'0'存储到变量'cnt'中，以计算总对的反转次数。
然后将名为pb的对象初始化为基于策略的变量'pbds'，以执行数组元素的插入和顺序配对。
初始化变量后，使用for 循环迭代数组元素。此数组元素将根据以下两个语句进行反转运算 -
cnt += i-pb.order_of_key(arr[i]); - 通过计算诸如 <5,4>、<5,3>、<5,2>、<5,1>、<4,3>、<4,2> 之类的对值，返回第二个参数中的最小值。等等。
pb.insert(arr[i]); − 通过使用预定义函数 insert()，我们添加数组元素 arr[i] 的反转。
我们启动主函数并声明向量数组输入。
然后，我们借助 'count' 变量调用函数 'inversion_Cnt'。
最后，'count' 变量给出数组中反转的总数。
示例
在此程序中，我们将使用基于策略的数据结构来计算数字的反转次数。
#include <iostream>
#include <vector>
// *******g++ header file*********
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
double long inversion_Cnt( vector<int>& arr) {
double long cnt = 0;
pbds pb;
for(int i = 0; i < arr.size(); i++) {
cnt += i-pb.order_of_key(arr[i]);
pb.insert(arr[i]); // add the array element
}
return cnt;
}
int main() {
vector<int> arr = {5, 4, 3, 2, 1}; // The inversion of following input array is <5,4>, <5,3>, <5,2>, <5,1>, <4,3>, <4,2>, <4,1>, <3,2>, <3,1>, <2,1>
double long count = inversion_Cnt(arr);
cout<<"使用基于策略的数据结构的反转计数总数为: "<<count<<endl;
return 0;
}
输出
使用基于策略的数据结构的反转计数总数为: 10
结论
我们通过执行基于反转计数的程序探索了 Linux 头文件 (g++) 的概念。众所周知，C++ 程序用于操作系统，它有一个跟踪器来记录系统的所有信息。与该程序相同的方式，我们可以看到子树是如何跟踪其每个节点的。
