Chenyuze24 @ 2025-01-11 11:29:54
小龙虾有一个由 n 个正整数组成的序列 {a₁, a₂,..., aₙ}，其中 2 ≤ n ≤ 10⁶ 且 1 ≤ aᵢ ≤ n。
对于序列的所有区间 [i, j]（1 ≤ i < j ≤ n），定义两个函数 c(i, j) 和 d(i, j)：
c(i, j) 的定义：
若 aᵢ = aⱼ，则 c(i, j) 等于区间 [i, j] 中比两端（即 aᵢ）大的元素的个数。 若 aᵢ ≠ aⱼ，则 c(i, j) = 0。
d(i, j) 的定义： 若区间 [i, j] 的长度（即 j - i + 1）是奇数，则 d(i, j) = 1。 若区间 [i, j] 的长度是偶数，则 d(i, j) = 2。 要求计算序列 a 中所有区间的 c(i, j) × d(i, j) 之和。
输入描述 第一行输入一个整数 n，表示序列中的元素个数。 第二行输入 n 个整数 a₁, a₂,..., aₙ，表示序列中的元素。
输出描述 在一行中输出一个整数，代表所有 c(i, j) × d(i, j) 之和。
示例 1 输入：
6 1 1 4 5 1 4
输出：
8
说明： 在这个样例中，除 c(1, 5) = 2、c(2, 5) = 2、c(3, 6) = 1 外，其余 c(i, j) 均为 0。 对于非零的 c(i, j)，d(1, 5) = 1、d(2, 5) = 2、d(3, 6) = 2。 最终计算结果为 2×1 + 2×2 + 1×2 = 8。
数据范围与提示
对于40%的数据，n ≤ 1000.
对于另外100%的数据，n ≤ 100000.
by bsdsdb @ 2025-01-11 11:40:35
@Chenyuze24 这是你们作业吗
by IOI_winner @ 2025-01-11 11:42:39
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
long long calculate_sum(int n, const vector<int>& a) {
unordered_map<int, vector<int>> index_map;
for (int i = 0; i < n; ++i) {
index_map[a[i]].push_back(i);
}
long long total_sum = 0;
for (const auto& entry : index_map) {
const vector<int>& indices = entry.second;
for (size_t i = 0; i < indices.size(); ++i) {
for (size_t j = i + 1; j < indices.size(); ++j) {
int start = indices[i];
int end = indices[j];
int count = 0;
for (int k = start + 1; k < end; ++k) {
if (a[k] > a[start]) {
++count;
}
}
int length = end - start + 1;
int d = (length % 2 == 1) ? 1 : 2;
total_sum += (long long)count * d;
}
}
}
return total_sum;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
cout << calculate_sum(n, a) << endl;
return 0;
}by Chenyuze24 @ 2025-01-11 12:06:53
@bsdsdb是的
by Chenyuze24 @ 2025-01-11 12:09:56
@IOI_winner 10个测试点 5个Wrong Answer 5个Time Exceeded
by Chenyuze24 @ 2025-01-11 12:11:24
这道题洛谷里有相似的吗 难度差不多普及+/提高