诈尸了!!! 浅浅浅浅浅浅谈树状数组 + 洛谷P1908 逆序对模板题
咕咕咕,N年没写过博客了,至于为什么,当然是因为懒,自从写上次博客到现在1个月半了,想想自己都学了什么。
开始之前先写篇小作文吧,233。
50天能干什么,50天够一个acm小白从零基础学完数据结,50天能够我骑行横跨中国,50天可以让一个人瘦20斤或胖20斤。50天,珠穆朗玛峰又升高了0.25厘米。当年戊戌变法,百日维新也就是50天的两倍,50天可以在我们这个国家开个大会,修改个宪法。50天,有无数的生命在终点寂静,有无数的生命在地球上降临。时间这个标尺是克苏恩体系下的力量之泉,骨肉在沙漏里化为尘埃,飘然滚下。用50天去谈论千万光年的星系,海底两万米下的水分子,矿山上的石头都是啼笑皆非,但正是一粒粒的尘沙构成了浩瀚无垠的时之沙漏,正是我们已知的110多种元素,构成了我们人类所能理解的宇宙万物表象。《旧约 传道书》里说“日光之下,并无新事”。人是情感性动物,社会性动物,带着自己的情绪一路向前,在黑格尔的虚假目标下前行,像浮士德一样寻找着自己也未知的生活,成为的未知之人。
这50天看了十几本书,看了40部电影美剧英剧日剧,参加了省赛,拿了个铜牌,这50天看了学长们一路金牌,深叹差距,自愧不如,这50天开始对大学的课程毫无兴趣,只想敲敲代码,50天从冬被换到了凉席,不知道下一个50天又是怎样的。
步入正题。
- 马拉车算法:求最最长回文子串的。
- 数位dp:数位dp的题可以说是板子题。只要知道怎么分解条件,打个模板就a了。注意前导0,这个前导0坑过我两次了。
- Nim博弈:这个玩意,打个了sg的模板题,这个说不上会,博弈的游戏分解核心是一个主游戏的胜负分解为子游戏的胜负。
- 接下来就是我要说的树状数组了,说些我在树状数组里理解到的东西。
树状数组的思想在于二进制下的区间前缀和,每一个编号i都是一个区间**i到 i-lowbit(i)**的前缀和信息。
将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;
}
下一篇: 树状数组