欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

诈尸了!!! 浅浅浅浅浅浅谈树状数组 + 洛谷P1908 逆序对模板题

程序员文章站 2022-03-21 19:33:24
...

咕咕咕,N年没写过博客了,至于为什么,当然是因为懒,自从写上次博客到现在1个月半了,想想自己都学了什么。

开始之前先写篇小作文吧,233。
50天能干什么,50天够一个acm小白从零基础学完数据结,50天能够我骑行横跨中国,50天可以让一个人瘦20斤或胖20斤。50天,珠穆朗玛峰又升高了0.25厘米。当年戊戌变法,百日维新也就是50天的两倍,50天可以在我们这个国家开个大会,修改个宪法。50天,有无数的生命在终点寂静,有无数的生命在地球上降临。时间这个标尺是克苏恩体系下的力量之泉,骨肉在沙漏里化为尘埃,飘然滚下。用50天去谈论千万光年的星系,海底两万米下的水分子,矿山上的石头都是啼笑皆非,但正是一粒粒的尘沙构成了浩瀚无垠的时之沙漏,正是我们已知的110多种元素,构成了我们人类所能理解的宇宙万物表象。《旧约 传道书》里说“日光之下,并无新事”。人是情感性动物,社会性动物,带着自己的情绪一路向前,在黑格尔的虚假目标下前行,像浮士德一样寻找着自己也未知的生活,成为的未知之人。

这50天看了十几本书,看了40部电影美剧英剧日剧,参加了省赛,拿了个铜牌,这50天看了学长们一路金牌,深叹差距,自愧不如,这50天开始对大学的课程毫无兴趣,只想敲敲代码,50天从冬被换到了凉席,不知道下一个50天又是怎样的。

步入正题。

  1. 马拉车算法:求最最长回文子串的。
  2. 数位dp:数位dp的题可以说是板子题。只要知道怎么分解条件,打个模板就a了。注意前导0,这个前导0坑过我两次了。
  3. Nim博弈:这个玩意,打个了sg的模板题,这个说不上会,博弈的游戏分解核心是一个主游戏的胜负分解为子游戏的胜负。
  4. 接下来就是我要说的树状数组了,说些我在树状数组里理解到的东西。

树状数组的思想在于二进制下的区间前缀和,每一个编号i都是一个区间**i到 i-lowbit(i)**的前缀和信息。
诈尸了!!! 浅浅浅浅浅浅谈树状数组 + 洛谷P1908 逆序对模板题

将C[]数组的结点序号转化为二进制

1=(001) C[1]=A[1];

2=(010) C[2]=A[1]+A[2];

3=(011) C[3]=A[3];

4=(100) C[4]=A[1]+A[2]+A[3]+A[4];

5=(101) C[5]=A[5];

6=(110) C[6]=A[5]+A[6];

7=(111) C[7]=A[7];

8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

对照式子可以发现 C[i]=A[i-2k+1]+A[i-2k+2]+…A[i];
(k为i的二进制中从最低位到高位连续零的长度)例如i=8时,k=3;

可以自行带入验证;

现在引入lowbit(x)

lowbit(x) 其实就是取出x的最低位1 换言之 lowbit(x)=2^k k的含义与上面相同

下面说代码

int lowbit(int t) {return t&(-t); }
-t 代表t的负数 计算机中负数使用对应的正数的补码来表示
例如 :
 t=6(0110) 此时 k=1
-t=-6=(1001+1)=(1010)
 t&(-t)=(0010)=2=2^1

C[i]=A[i-2^ k+1]+A[i-2^k+2]+…A[i];

C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+…A[i];

这段代码区域是转载。

区间查询

ll getsum(int num){
    ll res = 0;
    for(int i = num; i >= 1 ; i -= lowbit(i))
        res+=c[i];
    return res;
    //res = a[1]+a[2]+a[3]+.....+a[num];
}

先说题目洛谷P1908 逆序对
输入格式:
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。序列中每个数字不超过1e9。

输出格式:
给定序列中逆序对的数目。

输入
6
5 4 2 6 3 1

输出
11

说明
对于25%的数据,n≤2500.
对于50%的数据,n≤4×10^4.
对于所有数据,n≤5×10^5.
数会有重复的。

利用树状数组区间查询,我们求逆序对就可以实现,第m次存一个第k小的数,这次插入,多的逆序对是之前有多少比k大的。所以也就是用m减去前k的前缀和。
为什么存第k小,因为我们树状数组也是得开数组,如果不改成第k小,而是直接查询1~a[i]有多少个,那数组得开c[1e9]肯定不行,数据最多给1e5个数,所以我们改成第k小小就可以只开1e5大的数组了。

离散化简单说一下,就是开个带编号的结构体,按大小排序好,初始k等于0;
拍好序后给按照依次让其编号=k。注意重复的数。

for(int i = 1; i <= n; i++) {
        if(p[i].x != p[i-1].x) k++;
        arr[p[i].num] = k;
    }

求逆序对的过程:就是我上边说的,看看多少个比这个添加的数小,已经插入的个数减一下。我的num表示已经插入多少个数了。

for(int i = 1; i <= n; i++){
        tot += num - getsum(arr[i]);
        add(arr[i], 1); num++;
    }
/* warm heart, wagging tail,and a smile just for you!
//
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/`---'\____
//                      .'  \|     |//  `.
//                     /  \|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \\  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  `-`  ___/-. /
//                  ___`. .'  /--.--\  `. . __
//               ."" '<  `.___\_<|>_/___.'  >'"".
//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//              \  \ `-.   \_ __\ /__ _/   .-` /  /
//         ======`-.____`-.___\_____/___.-`____.-'======
//                            `=---='
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                     佛祖保佑      永无BUG
*/

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define FOR(a, b, c) for(int a = b; a <= c; a++)
#define met(a, b) memset(a, b, sizeof(a))
#define mid (l+r)/2
using namespace std;
int lowbit(int x){return x & (-x);}
struct node{
    int x, num;
}p[555555];
int cmp(node a, node b){
    return a.x < b.x;
}
ll arr[555555], c[555555], n;
void add(int num, int x){
    for(int i = num; i <= n; i += lowbit(i))
        c[i] += x;
    //这个是更新,想一下前缀和,比如sum【i】= a[1]+a[2]+.....a[i].
    //我们更新个a[3],那么我们sum[3] sum[4]...sum[i]都得更新。
}

ll getsum(int num){
    ll res = 0;
    for(int i = num; i >= 1 ; i -= lowbit(i))
        res+=c[i];
    return res;
    //res = a[1]+a[2]+a[3]+.....+a[num];
}

int main()
{
	met(c, 0); met(arr, 0); met(p, 0);
    ios; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i].x;
        p[i].num = i;
    }
    sort(p+1, p+1+n, cmp);
    int k = 0;
    for(int i = 1; i <= n; i++) {
        if(p[i].x != p[i-1].x) k++;
        arr[p[i].num] = k;
    }
    ll tot = 0; //逆序对个数
    int num = 0; //表示已经插入几个数了
    for(int i = 1; i <= n; i++){
        tot += num - getsum(arr[i]);
        add(arr[i], 1); num++; //把这个数从插入,并且个数加一
    }
    cout << tot;
    return 0;
}

相关标签: 树状数组