每日一题【#1】
本帖最后由 Ewan-Ahiouy 于 2023-8-25 12:01 编辑区间求和与排序
题目描述
给定一个包含 n 个正整数的数组 a，你需要回答 t 个询问。每个询问给出两个整数 l 和 r，要求计算数组 a 在区间 内的元素之和，并让数组 部分从大到小排序，最后输出数组 a。
输入格式
第一行一个整数 n 。
第二行 n 个整数 a_i，用空格分隔。
第三行一个整数 t 。
接下来 t 行，每行两个整数 l_i, r_i，用空格分隔。
输出格式
每次查询返回区间 的和，并将数组 部分从大到小排序（排序不影响区间和，你可以想成两个数组，一个排序，一个求和），查询结束后最后返回数组 a （排序过的），用空格分隔。
输入输出样例
样例输入 #1
5
1 2 3 4 5
2
1 3
3 5
样例输出 #1
6
12
3 2 5 4 1
样例输入 #2
10
2 4 6 8 10 1 3 5 7 9
5
1 10
5 6
2 8
4 9
3 7
样例输出 #2
55
11
37
34
28
10 9 8 7 6 5 4 3 2 1
样例解释
【样例 #1 解释】
第一行：为第一次询问，区间 的和为6，并将数组 区间进行降序排序。
第二行：为第二次询问，区间 的和为12，并将数组 区间进行降序排序。
第三行：查询结束，返回现在的数组。
数据范围
对于 100% 的数据， 1 ≤ n ≤ 10^5 ， 1 ≤ t ≤ 10^3 ， 1 ≤ l_i < r_i ≤ n，1 ≤ a_i ≤ 10^3。
测试链接 -> https://www.luogu.com.cn/problem/U332137
本帖最后由 zhangjinxuan 于 2023-8-25 11:18 编辑
排序不能优化，就懒得写前缀和了{:10_248:}
#include <bits/stdc++.h>
using namespace std;
int n, a, t, l, r, b;
bool cmp(const int &a, const int &b) {
return a > b;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a);
b = a;
}
scanf("%d", &t);
while (t--) {
scanf("%d%d", &l, &r);
long long sum = 0;
for (int i = l; i <= r; ++i) sum += a;
sort(b + l, b + r + 1, cmp);
printf("%lld\n", sum);
}
for (int i = 1; i <= n; ++i) {
printf("%d ", b);
}
return 0;
} @额外减小 @tommyyu @zhangjinxuan @sfqxx @isdkz @Mike_python小 @陈尚涵 来看看啊{:10_256:} 可以离线做欸，但是给区间离散化又麻烦{:10_277:} cao，好像不能离线 zhangjinxuan 发表于 2023-8-25 10:59
可以离线做欸，但是给区间离散化又麻烦
想到什么地方去了？{:10_277:}很基础的算法{:10_277:} Ewan-Ahiouy 发表于 2023-8-25 11:02
想到什么地方去了？很基础的算法
查询一次做一次排序？ zhangjinxuan 发表于 2023-8-25 11:05
查询一次做一次排序？
你算算复杂度 哈哈，这不就是进阶篇那个前缀和啊 Ewan-Ahiouy 发表于 2023-8-25 11:06
你算算复杂度
bushi，题目不是这么说的吗，查询一次做一次排序 sfqxx 发表于 2023-8-25 11:07
哈哈，这不就是进阶篇那个前缀和啊
{:10_256:} zhangjinxuan 发表于 2023-8-25 11:05
查询一次做一次排序？
告诉你一个很好用的东西：氧气{:10_327:} Ewan-Ahiouy 发表于 2023-8-25 11:07
告诉你一个很好用的东西：氧气
臭氧(╯▔皿▔)╯ zhangjinxuan 发表于 2023-8-25 11:08
臭氧(╯▔皿▔)╯
不是，你暴力？我的想法是前缀和来着{:10_257:}不行，得加大强度{:10_244:} zhangjinxuan 发表于 2023-8-25 11:09
感觉 std 有点问题，因为 std 可能是最后再做一遍排序，而题目要求是查询了就要排序，感觉很奇怪。
气死我了！造数据怎么这么难！{:10_244:} zhangjinxuan 发表于 2023-8-25 11:09
感觉 std 有点问题，因为 std 可能是最后再做一遍排序，而题目要求是查询了就要排序，感觉很奇怪。
？ Ewan-Ahiouy 发表于 2023-8-25 11:12
完了完了卧槽！丢脸丢尽了
想法只能暴力，因为时间复杂度瓶颈就在这个排序上{:10_266:}
即使前缀和优化也不能优化排序{:10_266:} Ewan-Ahiouy 发表于 2023-8-25 11:16
不是，为什么我要哭啊
不就是查询原数组的 l~r 吗？
如果真是这样的话就可以离线了{:10_257:}
好像还是不能 zhangjinxuan 发表于 2023-8-25 11:18
如果真是这样的话就可以离线了
好像还是不能
就是求排序后的数组，查询排序前的区间 Ewan-Ahiouy 发表于 2023-8-25 11:18
就是求排序后的数组，查询排序前的区间
那排序后的数组一定要 O(t n log n) 求解吗{:10_272:}
页:
[1]
2