从逆序对开始······
Mudrobøt
2018-03-23 23:39:55
#### 请对每一个你所学的知识保持一种尊敬的态度，千万不要说一个东西简单，是知识总会有他独特的价值，这也是为什么我要坚持写博客的一个原因！！！
[题目传送门](https://www.luogu.org/problemnew/show/P1908)
不得不说今天晚上听了一下大佬讲解的逆序对，确实感觉这个东西非常的神奇，因为我发现这个东西不仅仅是一个归并排序那么简单的东西，实际上背后还大有学问，虽然本人并没有学会这道题的基本解决方式，但是跟着大佬混总还是会学到一些东西的，那么今天我就来为大家介绍一下**离散化与动态开点**
在开始之前还是先允许我先介绍一下这道题大致的解题思路，方便引入我们今天的主题。
首先朴素算法是这样的，我们先从第一个数开始一直到最后一个数，然后每次循环它前面的数，然后发现比它大的就记录下来（cnt++），然后我们就会发现会非常的爆炸，因为这样子的话，复杂度O(n^2)，40000^2……我不在多说了。
下面说一说**比较**正常的做法，相信大家都学过桶排序吧！这道题比较正常的做法是这样的，我们边读边处理，不对不对，应该是我们先做好了**排序**后再来进行一个一个处理，首先我们搞一个**线段树**，然后树中放的全部都是桶，是的，你没有看错，就是桶，统计这个数以来出现了多少次，那么你可能就会有所感觉了，这道题不就是，每次进行一次单点修改，区间求和的线段树吗?对的，你能想到这一点，我忠心祝贺你！的确是这样，我们每一次加入一个数，然后对他**后**面区间进行求值，就求到它的逆序对了。对对对，但是你如果能够想到博主想到这个方法的一定是一个SB，那么你就更厉害了。数据范围不是1e9吗！！！我靠，1e9个桶，直接树都开炸！对啊对啊，所以这个时候，**离散化大法要出场了。**
### 离散化（李三花）
小蓝居然可以把离散化读成那个，我觉得它非常的厉害！！！！！
话不多说，开始我们的离散化吧！其实大家完全没有必要去看网上那些东西，特别是百度百科，简直有毒，我们现在还用不到那么牛逼的离散化，所以这里介绍的离散化是非常简单的一种。
所谓离散化，就是说你发现了这个逆序对这道题啊，非常的讨厌，数据这么大，那么我们可不可以适当的把数据范围缩小一点呢？其实是可以的，我们发现，逆序对这道题有一个特点，就是比如说数据2 1还是数据 203903123 1它都是一个逆序对，前面的数都是比1大，但是我们不用管他比1大多少，只要比1大就可以了，但是为我们可以明显感觉到我们要对后面的数据处理一下，否则就要开爆树，在这里我们只需要把它处理成2就可以达到相同的效果。
举例一下：
2 33423434 437834 25345 373 35 //就可以被换成
1 6 5 4 3 2 //效果一样
但是你可能会说哎呦，我还排个序，编个号，那个时候我怎么知道原来它是什么样子的啊？
结构体大法好！！！
离散化基本操作如下：
```
#include<bits/stdc++.h>
using namespace std;
struct sd{
int val,loc;//val是值 loc是当前点的位置
}x[100005];
bool cmp(sd a,sd b)
{
if(a.val<b.val)
return true;
}
int discretization[100005];//这单词真够长
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>x[i].val;
x[i].loc=i;
}
sort(x+1,x+n+1,cmp);
int cnt=0;
x[0].val=891881292;//important!
for(int i=1;i<=n;++i)
{
if(x[i-1].val==x[i].val)discretization[x[i].loc]=cnt;
else
{
cnt++;
discretization[x[i].loc]=cnt;
}
}
for(int i=1;i<=n;++i)
{
cout<<discretization[i]<<" ";
}
return 0;
}
```
打important的地方一定要注意，否则就要出事情！！！你想一想，如果我们呢第一个数为0那么那个cnt标记就不会++了！！！，恐怖！！！???
所以说我们离散化部分就讲完了，相信这道题你也应该可以A了。
标程代码：
```
#include<bits/stdc++.h>
#define ls(k) a[k].ch[0]
#define rs(k) a[k].ch[1]
using namespace std;
struct node {
int l,r,cnt,ch[2];
};node a[510000];
int cnt=1;
struct num {
int val;
int loc;
bool operator < (const num &a) const {
return val<a.val;
}
};
num lisanhua[51000];
int yingshe[51000];
int n;
void init() {
int cnt=0;
cin>>n;
for(int i=1;i<=n;++i) {
cin>>lisanhua[i].val;
lisanhua[i].loc=i;
}
sort(lisanhua+1,lisanhua+n+1);
lisanhua[0].val=19260817;
for(int i=1;i<=n;++i)
{
if(lisanhua[i].val!=lisanhua[i-1].val) yingshe[lisanhua[i].loc]=cnt+1,++cnt;
else yingshe[lisanhua[i].loc]=cnt;
}
}
void update(int k) {
a[k].cnt=a[ls(k)].cnt+a[rs(k)].cnt;
}
void build(int k,int l,int r) {
a[k].l=l;a[k].r=r;
if(l==r) return;
int mid=l+r;mid/=2;
ls(k)=cnt+1,++cnt,build(cnt,l,mid);
rs(k)=cnt+1,++cnt,build(cnt,mid+1,r);
}
void ins(int k,int val) {
if(a[k].l==a[k].r&&a[k].l==val) {
a[k].cnt++;
return;
}
int mid=a[k].l+a[k].r;mid/=2;
if(val<=mid) ins(ls(k),val);
else ins(rs(k),val);
update(k);
}
int query(int k,int l,int r) {
if(a[k].l==l&&a[k].r==r) {
return a[k].cnt;
}
int mid=a[k].l+a[k].r;mid/=2;
if(r<=mid) return query(ls(k),l,r);
else if(l>mid) return query(rs(k),l,r);
else return query(ls(k),l,mid)+query(rs(k),mid+1,r);
}
void prit(int k) {
printf("%d %d %d %d %d %d\n",k,ls(k),rs(k),a[k].l,a[k].r,a[k].cnt);
if(ls(k)!=0) prit(ls(k));
if(rs(k)!=0) prit(rs(k));
}
int main() {
build(1,0,51000);
init();
long long ans=0;
for(int i=1;i<=n;++i) {
ins(1,yingshe[i]);
ans+=query(1,yingshe[i]+1,n+1);
}
cout<<ans;
return 0;
}
```
#### 技巧：这里我们使用了先建树（空树）然后在modify的的写法，希望大家能够理解一下！
好了，就这样了，但是如果哪一天你就是说，哎呀这个离散化写着太让我烦恼了，那么有没有另外一种写法呢？很明显是有的，那么就是我们的**动态开点**了，这样子写有一个好处，就是我们不用写Buildtree啦！是不是听起来很爽呢？我们每次在push的时候就顺便把它的儿子女儿都建了，具体过程不在赘述，这里就贴一段动态开点建树的代码过程，其实大家只要认真的把代码看懂了，那么你就已经掌握到了动态开点建树的精髓了（**用了动态开点就可以不用离散化了哟！！**）！！！！！！
代码如下：
```
void modify(int k,int val)
{
if(node[k].l==node[k].r&&node[k].l==val)
{
node[k].cnt++;
return;
}
int mid=node[k].l+node[k].r;mid/=2;
if(node[k].son[0]==0)
{
cnt++;
node[k].son[0]=cnt;
node[cnt].l=node[k].l;node[cnt].r=mid;
}
if(node[k].son[1]==0)
{
cnt++;
node[k].son[1]=cnt;
node[cnt].l=mid+1;node[cnt].r=node[k].r;
}
if(val>mid)
{
modify(node[k].son[1],val);
}
else
{
modify(node[k].son[0],val);
}
update(k);
}
```
这只是征程的开始，线段树的精髓远远不止这些！！！
标程代码如下：
```
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
struct sd{
int son[2];
long long l,r,cnt;
}node[N];
int n;
int cnt=1;
long long ans;
void update(int k)
{
node[k].cnt=node[node[k].son[0]].cnt+node[node[k].son[1]].cnt;
}
void modify(int k,int val)
{
if(node[k].l==node[k].r&&node[k].l==val)
{
node[k].cnt++;
return;
}
int mid=node[k].l+node[k].r;mid/=2;
if(node[k].son[0]==0)
{
cnt++;
node[k].son[0]=cnt;
node[cnt].l=node[k].l;node[cnt].r=mid;
}
if(node[k].son[1]==0)
{
cnt++;
node[k].son[1]=cnt;
node[cnt].l=mid+1;node[cnt].r=node[k].r;
}
if(val>mid)
{
modify(node[k].son[1],val);
}
else
{
modify(node[k].son[0],val);
}
update(k);
}
long long query(int k,int ql,int qr)
{
if(k==0) return 0;//very very important！！！
if(node[k].l==ql&&node[k].r==qr)
{
return node[k].cnt;
}
else
{
int mid=(node[k].l+node[k].r)/2;
if(qr<=mid) return query(node[k].son[0],ql,qr);
else if(ql>mid) return query(node[k].son[1],ql,qr);
else
{
return query(node[k].son[0],ql,mid)+query(node[k].son[1],mid+1,qr);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
node[1].l=1; node[1].r=1e9+7;
int n,sth;
cin>>n;
ans=0;
for(int i=1;i<=n;++i)
{
cin>>sth;
modify(1,sth);
ans+=query(1,sth+1,1e9+7);
}
cout<<ans<<endl;
}
```
**关于动态开点的注意事项，我后面在写吧！！！**
于是我履行了诺言，下面就是动态开点最为重要的一个注意事项！！
大家认真的阅读一下代码，可以发现我在代码中加入了一个very very important 的标记，这里一定要写这句话，为什么呢？因为我们动态开点，开到叶节点的时候一定会遇到一种情况，就是叶节点并没有儿子，那么他的儿子编号就是0，所以在下一次递归中就会递归到0号节点，然后0号什么参数都是0，于是程序开始原地转圈，然后就爆炸了！！！！其实这道题写不写都可以，但是这里只是做一个小小的提醒！！！
这只是征程的开始，线段树的精髓远远不止这些！！！
By njc