本文主要是介绍分治算法，逆序对，三维偏序与CDQ分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分治算法基本思想
当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。
对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。
如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
归并排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,oo=2*1e9;
int n,L[maxn],R[maxn],a[maxn];
void merge(int l,int mid,int r){int n1=mid-l+1;int n2=r-mid;//r-(mid+1)+1for(int i=1;i<=n1;i++)L[i]=a[i+l-1];for(int i=1;i<=n2;i++)R[i]=a[i+mid];//i+(mid+1)-1L[n1+1]=oo;R[n2+1]=oo;//哨兵 int x=1,y=1;for(int i=l;i<=r;i++){if(L[x]<R[y])a[i]=L[x++];else a[i]=R[y++];}return ;
}
void solve(int l,int r){if(l>=r)return ;int mid=(l+r)/2;solve(l,mid);solve(mid+1,r);//分治 merge(l,mid,r);//合并子问题 return ;
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];solve(1,n);for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}用分治算法实现逆序对
P1908 逆序对
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,oo=2*1e9;
int n,L[maxn],R[maxn],a[maxn];
long long ans=0;
void merge(int l,int mid,int r){int n1=mid-l+1;int n2=r-mid;//r-(mid+1)+1for(int i=1;i<=n1;i++)L[i]=a[i+l-1];for(int i=1;i<=n2;i++)R[i]=a[i+mid];//i+(mid+1)-1L[n1+1]=oo;R[n2+1]=oo;//哨兵 int x=1,y=1;for(int i=l;i<=r;i++){if(L[x]<R[y])a[i]=L[x++];else a[i]=R[y++];}x=y=1;while(y<=n2){if(L[x]>R[y])ans+=n1-x+1,y++;//计算逆序对的数量 else x++; }return ;
}
void solve(int l,int r){if(l>=r)return ;int mid=(l+r)/2;solve(l,mid);solve(mid+1,r);//分治 merge(l,mid,r);//合并子问题 return ;
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];solve(1,n);cout<<ans;return 0;
}
二维偏序
定义：
形如 xi<xjx_i<x_jxi<xj 且 yi<yjy_i<y_jyi<yj 之类的约束条件，我们可以称为二维偏序。
逆序对就是一个非常经典的二位偏序。
解决：
如果按照暴力想法，我们 O(n2)O(n^2)O(n2)的时间枚举 i,ji,ji,j,这样太慢了。
处理第 iii 位时，我们已经处理过 [1,i−1]\left[ 1,i-1 \right][1,i−1] 的数量，那么我们可不可以用一个数据结构记录一下之前的情况呢？
这就引出了二维偏序。
我们把第一维从小到大排序，然后遍历，将第二位插入树状数组中，每次查询，即可解决问题。
例题：
有n个学生，第i个学生有两个技巧：x[i]x\left[ i \right]x[i] 和 y[i]y\left[ i \right ] y[i] ，不存在两个学生的技巧完全相同。
如果 x[j]≤x[i]x[j]\leq x[i]x[j]≤x[i] 且 y[j]≤[i]y[j]\leq [i]y[j]≤[i] ，那么学生 iii 就是比学生 jjj 强，学生 jjj 比学生 iii 弱。
假设总共有 aaa 个学生比第 iii 个学生弱，那么第 iii 个学生的等级就是 aaa 。
现在的问题是，依次输出：
有多少个学生的等级是 000 ？
有多少个学生的等级是 111 ？
有多少个学生的等级是 222 ？
......
有多少个学生的等级是 n−1n-1n−1 ?
输入格式
第一行，一个整数nnn。1≤n≤1000001\leq n\leq 1000001≤n≤100000。
接下来n行，第i行有两个整数x[i]x[ i ]x[i]和y[i]y[ i ]y[i]。 1≤x[i],y[i]≤10000001\leq x[i],y[i]\leq 10000001≤x[i],y[i]≤1000000
输出格式
共nnn行，每行一个整数。
输入：
5
1 1
5 1
7 1
3 3
5 5
输出：
1 2 1 1 0
这篇关于分治算法，逆序对，三维偏序与CDQ分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
