hdu1394

传送门

本题就是求循环移位后逆序数的最小值。
其实主要就是求序列的逆序数。
逆序数的求法很多,可以用归并排序求。
也可以用树状数组和线段树求逆序数。

逆序数求得之后,把第一个数移到最后的逆序数是可以直接得到的。
比如原来的逆序数是ans,把a[0]移到最后,减少逆序数a[0],同时增加逆序数n-a[0]-1个,就是ans-a[0]+n-a[0]-1;

只要i从0-n-1循环一遍取最小值就可以了。

代码

树状数组(AC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 5050;
int n, e[maxn];

int lowbit(int k){
return k & (-k);
}

void add(int k, int v){
while(k <= n){
e[k] += v;
k += lowbit(k);
}
}

int sum(int k){
int re = 0;
while(k > 0){
re += e[k];
k -= lowbit(k);
}
return re;
}

int a[maxn];

int main(){
while(~scanf("%d", &n)){
int ans = 0;
memset(e, 0, sizeof(e));
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
a[i]++;
ans += sum(n) - sum(a[i]);
add(a[i], 1); //注意这里e[k]并没有初始化为a[k],而是用到了类似差值的思想
}
int Min = ans;
for(int i = 1; i <= n; i++){
ans += n - a[i] - (a[i] - 1);
if(ans < Min) Min = ans;
}
printf("%d\n", Min);
}
return 0;
}

树状数组

什么是树状数组?

就是用数组来模拟树形结构,可以解决大部分基于区间上的更新以及求和问题。树状数组可以解决的问题都可以用线段树解决,这两者的区别在哪里呢?树状数组修改和查询的复杂度都是 O(log n),而且相比线段树系数要少很多,比传统数组要快,而且容易写。缺点是遇到复杂的区间问题还是不能解决,功能还是有限。树状数组多用于高效计算数列的前缀和。

核心思想

(1) 树状数组中的每个元素是原数组中的一个或多个连续元素的和;

(2) 在进行连续求和时,只需要将树状数组中某几个元素进行求和;

(3) 在对某一个元素进行修改时,只需要修改树状数组中某几个元素的和即可。

(4) 用 A 表示原始数组,C 表示树状数组,则:C[i] = A[i - 2^k + 1] + A[i - 2^k + 2] + … + A[i];k为 i 的二进制中末尾连续的 0 的个数。

C[1] = A[1];

C[2] = A[1] + A[2];

C[3] = A[3];

C[4] = A[1] + A[2] + A[3] + A[4];

C[5] = A[5];

C[6] = A[5] + A[6];

C[7] = A[7];

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

(5) C 中元素的后继(为此结点的父结点):结点的后继是比它大、最近的且编号末尾连续 0 比它多的结点。

(6) C 中元素的前驱:结点的前驱为比它小、最近的且末尾连续 0 的个数比它多的结点。前驱主要用来计算连续和。

例如 i = 8(1000) 时候,k = 3,可自行验证。

这个怎么实现求和呢,比如我们要找前 7 项和,那么应该是 SUM = C[7] + C[6] + C[4];

而根据上面的式子,容易的出 SUM[i] = C[i] + C[i - 2 ^ k1] + C[(i - 2 ^ k1) - 2 ^ k2] + …..;

其实树状数组就是一个二进制上面的应用。

现在新的问题来了:2 ^ k 该怎么求呢,不难得出 2 ^ k = i & (i ^ (i - 1));但这个还是不好求出呀,于是就有:2 ^ k = i & (- i);

为什么呢?

这里利用的负数的存储特性,负数是以补码存储的,对于整数运算 x & (-x) 有:

当 x 为 0 时,即 0 & 0,结果为 0;

当 x 为奇数时,最后一个比特位为 1,取反加 1 没有进位,故 x 和 - x 除最后一位外前面的位正好相反,按位与结果为 0。结果为 1。

当 x 为偶数,且为 2 的 m 次方时,x 的二进制表示中只有一位是 1(从右往左的第 m + 1 位),其右边有 m 位 0,故 x 取反加 1 后,从右到左第有 m 个 0,第 m + 1 位及其左边全是 1。这样,x & (- x) 得到的就是 x。

当 x 为偶数,却不为 2 的 m 次方的形式时,可以写作 x = y * (2 ^ k)。其中,y 的最低位为 1。实际上就是把 x 用一个奇数左移 k 位来表示。这时,x 的二进制表示最右边有 k 个 0,从右往左第 k + 1 位为 1。当对 x 取反时,最右边的 k 位 0 变成 1,第 k + 1 位变为 0;再加 1,最右边的 k 位就又变成了 0,第 k + 1位因为进位的关系变成了 1。左边的位因为没有进位,正好和 x 原来对应的位上的值相反。二者按位与,得到:第 k + 1 位上为 1,左边右边都为 0。结果为 2 ^ k。

总结一下:x & (-x),当 x 为 0 时结果为 0;x 为奇数时,结果为 1;x 为偶数时,结果为 x 中 2 的最大次方的因子。

而且这个有一个专门的称呼,叫做 lowbit,即取 2 ^ k。

基本操作

1.预备函数 lowbit(int)

树状数组最基本的操作就是找到前驱和后继。lowbit 函数返回将参数转化为二进制后最后一个 1 所在的位置转化为十进制后的值。例如,34 转化二进制为 100010,最后一个 1 在第二位,所以返回 10, 即 2 。

1
2
3
int lowbit(int k){
return k & (-k);
}

2.修改原始数据某一元素的值

将 a[k] 的值增加 v ,需要把 e[k] 以及其后继结点的值全部加 k ,一直到 LEN (数组最大长度)。

1
2
3
4
5
6
7
8
#define LEN 100
int e[LEN];
void add(int k, int v){
while(k < LEN){
e[k] += v;
k += lowbit(k);
}
}

3.求原始数据前 k 项的和

只需要把 e[k] 以及其前驱结点的值累加即可。

1
2
3
4
5
6
7
8
int sum(int k){
int re = 0;
while(k > 0){
re += e[k];
k -= lowbit(k);
}
return re;
}

代码实现

模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int n;
int a[50005],c[50005]; //对应原数组和树状数组

int lowbit(int x){
return x & (-x);
}

void update(int i,int k){ //在i位置加上k
while(i <= n){
c[i] += k;
i += lowbit(i);
}
}

int getsum(int i){ //求A[1 - i]的和
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}

int main(){
int t;
cin >> t;
for(int tot = 1; tot <= t; tot++){
cout << "Case " << tot << ":" << endl;
memset(a, 0, sizeof a);
memset(c, 0, sizeof c);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
update(i, a[i]); //输入初值的时候,也相当于更新了值
}

string s;
int x, y;
while(cin >> s && s[0] != 'E'){
cin >> x >> y;
if(s[0] == 'Q'){ //求和操作
int sum = getsum(y) - getsum(x-1); //x-y区间和也就等于1-y区间和减去1-(x-1)区间和
cout << sum << endl;
}
else if(s[0] == 'A'){
update(x, y);
}
else if(s[0] == 'S'){
update(x, -y); //减去操作,即为加上相反数
}
}

}
return 0;
}

树状数组的几种变式(区间更新,区间查询)

1.单点更新、单点查询

2.单点更新、区间查询

3.区间更新、单点查询

这就是第一个问题,如果题目是要把 x - y 区间内的所有值全部加上 k 或者减去 k ,然后查询操作是问某个点的值。如果是像上面的树状数组来说,就必须把 x - y 区间内每个值都更新,这样的复杂度肯定是不行的,这个时候,就不能再用数据的值建树了,这里我们引入差分,利用差分建树。

假设我们规定 A[0] = 0,则有 A[i] = ΣD[j] (D[j] = A[j] - A[j - 1])。那么当某个区间 [x, y] 值改变了,区间内的差值是不变的,只有 D[x] 和 D[y + 1] 的值发生改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n;
int a[50005] = {0};
int sum1[50005]; //(D[1] + D[2] + ... + D[n])
int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x){
return x & (- x);
}

void update(int i, int k){
int x = i; //因为x不变,所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x - 1);
i += lowbit(i);
}
}

int getsum(int i){ //求前缀和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}

int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
update(i, a[i] - a[i - 1]); //输入初值的时候,也相当于更新了值
}

//[x,y]区间内加上k
update(x, k); //A[x] - A[x-1]增加k
update(y + 1, - k); //A[y+1] - A[y]减少k

//求[x,y]区间和
int sum = getsum(y) - getsum(x - 1);

return 0;
}

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.