UVA1260 题解

题目大意

给定每天的销售额列表

A

，对第

i

天（

i≥2

），计算之前所有天数中销售额小于或等于

A_i

的天数，存入

B_{i-1}

。求所有

B_i

的总和。

输入有多个测试用例，每个用例给出

n

和

A

数组。输出每个用例的B数组总和。其中

n≤1000

，

A_i≤5000

。

AC 方法 1——暴力

因为这道题的数据范围实在是太弱了，导致

O(T·n^2)

的代码也能过。所以只需要暴力枚举枚举所有

a_k\leq a_i

的情况并统计就行了。

参考代码

CPP

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
using namespace std;
int a[1005];
signed main() {
	fast_running;
	int T;
	cin >> T;
	while (T--) {
		int n, ans = 0;
		cin >> n;
		for (Rint i = 1; i <= n; i++) cin >> a[i];
		for (Rint i = 2; i <= n; i++) {
			for (Rint k = 1; k < i; k++) {
				if (a[k] <= a[i]) ++ans;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

AC 方法 2——树状数组

方法 1 实在是过于暴力了，虽然 AC 这道题不难，但要是遇到范围稍微大一点的类似的题，那该如何？

我们可以使用树状数组或线段树维护前缀和的方法，将查询和更新的时间复杂度降为

O(T·n·\log M)

，其中

M

是数值的最大值。那么给如何做呢？这里我们将对树状数组进行详解

首先我们要了解树状数组的作用：

动态单点更新 update(x, 1)：记录数值 $x$ 的出现次数。
前缀和查询 query(x)：查询 $≤ x$ 的元素个数。

树状数组的实现

CPP

int BIT[5005]; // 树状数组，A[i] ≤ 5000

// 更新：在位置x增加val
void update(int x, int val) {
    for (; x <= 5000; x += x & -x)
        BIT[x] += val;
}

// 查询：统计 ≤x 的元素个数
int query(int x) {
    int res = 0;
    for (; x > 0; x -= x & -x)
        res += BIT[x];
    return res;
}

x & -x：获取 $x$ 的二进制最低位的 $1$ （如 $6\ \& -6 = 2$ ）。
update(x, 1)：表示数值 $x$ 出现了一次。
query(x)：返回 $≤ x$ 的元素总数。

主逻辑

CPP

int sum = 0;
memset(BIT, 0, sizeof(BIT)); // 初始化树状数组

for (int i = 1; i <= n; i++) {
    if (i > 1) {
        sum += query(A[i]); // 查询 ≤A[i] 的个数
    }
    update(A[i], 1); // 将 A[i] 加入树状数组
}

对 $i ≥ 2$ ，查询 $≤ A_{i}$ 的元素个数（query(A[i])），并累加到 sum。
更新树状数组，记录 $A_{i}$ 的出现次数（update(A[i], 1)）。

完整代码

CPP

#include <bits/stdc++.h>
using namespace std;

int BIT[5005];

void update(int x, int val) {
    for (; x <= 5000; x += x & -x)
        BIT[x] += val;
}

int query(int x) {
    int res = 0;
    for (; x > 0; x -= x & -x)
        res += BIT[x];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, sum = 0;
        cin >> n;
        memset(BIT, 0, sizeof(BIT));

        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (i > 1) {
                sum += query(x);
            }
            update(x, 1);
        }
        cout << sum << '\n';
    }
    return 0;
}

文章操作