CDOJ1583-树状数组（2017 UESTC Training for Data Structures）

分手后的思念是犯贱 2022-06-13 08:24 68阅读 0赞

**传送门：[CDOJ1583][]**

**题目大意：**

给你两个n个数的排列，问你从第一个排列通过交换相邻的数变为第二个排列的最小步数

**题目思路：**

因为只能交换相邻的数，所以我们可以贪心想到直接按顺序从左到右将第一个变为第二个，

所一每个数的交换次数为移动到终点位置的距离，这里我们可以很好想到树状数组来处理

我们先求出第一个排列只的数在第二个中的排名数组，然后求排名数组的逆序数对就是答案

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 2e5+100;
    int n;
    int a[maxn];
    int get(int x){return x&(-x);}
    void updata(int x){while(x<=n){a[x]++,x+=get(x);}}
    int sum(int x){int res = 0;while(x>0){res+=a[x],x-=get(x);}return res;}
    int ss[maxn],tt[maxn],rk[maxn];
    int main()
    {
        long long ans = 0;
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",&ss[i]);
        for(int i=1;i<=n;i++)scanf("%d",&tt[i]);
        for(int i=1;i<=n;i++)rk[tt[i]] = i;
        for(int i=1;i<=n;i++)tt[i] = rk[ss[i]];
        for(int i=1;i<=n;i++){ans+=(long long)(i-1-sum(tt[i]));updata(tt[i]);}
        cout<<ans<<endl;
        return 0;
    }

[CDOJ1583]: http://acm.uestc.edu.cn/#/problem/show/1583

发表评论取消回复

表情：

评论列表（有 0 条评论，68人围观）

还没有评论，来说两句吧...

相关阅读

相关 data structure --Queue(基于数组的实现)

include<iostream> using namespace std; const int maxqueue=10; template <

「爱情、让人受尽委屈。」/ 2022年09月20日 05:55/ 0 赞/ 124 阅读

相关 CDOJ1601 - 二维树状数组（2017 UESTC Training for Data Structures）

传送门：[CDOJ1601][] 题目思路：题目可以抽象为在一个坐标系中初始时所有点都为0，然后有m次操作，有两种 1，将一个矩形中的所有点都异或1,0变1,

╰半橙微兮°/ 2022年06月13日 09:19/ 0 赞/ 73 阅读

相关 CDOJ1600-矩形切割（2017 UESTC Training for Data Structures P）

传送门：[CDOJ1600][] 题目大意：在一个二维平面坐标系上给你n个矩形，求n个矩形并集的面积，矩形平行坐标轴题目思路：

迈不过友情╰/ 2022年06月13日 09:19/ 0 赞/ 78 阅读

相关 CDOJ1590-dfs+树链剖分（2017 UESTC Training for Data Structures O）

传送门：[CDOJ1590][] 题目大意：给你一颗n个节点的树，根为T，初始时所有节点的值为0，然后给你m次操作，三种操作 1，更新一个

布满荆棘的人生/ 2022年06月13日 09:18/ 0 赞/ 85 阅读

相关 CDOJ1598-线段树合并（2017 UESTC Training for Data Structures G）

传送门：[CDOJ1598][] 题目大意：给你n个数m次操作，有两种操作 1，询问区间\[a,b\]的最大连续子区间 2，将第pos

港控/mmm°/ 2022年06月13日 08:24/ 0 赞/ 104 阅读

相关 CDOJ1583-树状数组（2017 UESTC Training for Data Structures）

传送门：[CDOJ1583][] 题目大意：给你两个n个数的排列，问你从第一个排列通过交换相邻的数变为第二个排列的最小步数题目思路：因为只能交

分手后的思念是犯贱/ 2022年06月13日 08:24/ 0 赞/ 69 阅读

相关 CDOJ1597-线段树好题（2017 UESTC Training for Data Structures C）

传送门：[CDOJ1597][] 题目大意：给你一个长度为n的序列，m次操作，三种操作： 1.给一段区间内的每个数乘上一个非负整数。 2.给一段区间内的每个

曾经终败给现在/ 2022年06月13日 08:23/ 0 赞/ 112 阅读

相关 CDOJ-1592 (2017 UESTC Training for Data Structures B)

传送门：[CDOJ1592][] 题目大意：给你一个长度为n的序列，只有1和0，m次操作，两种操作，第一种为将一段区间异或上0，一种为询问一段区间最长连续1

男娘i/ 2022年06月13日 08:23/ 0 赞/ 81 阅读

相关 CDOJ-1591（2017 UESTC Training for Graph Theory -A）

A - An easy problem A Time Limit: 1000/1000MS (Java/Others) Memory Limit: 65535/

客官°小女子只卖身不卖艺/ 2022年06月13日 08:23/ 0 赞/ 126 阅读

相关 2018 UESTC Training for Data Structures--并查集

I.不如把并查集加上个计数功能吧给并查集加上计数功能 include <bits/stdc++.h> using namespace std;

我就是我/ 2021年09月15日 17:10/ 0 赞/ 151 阅读