[已解决]每日一题【#1】

Ewan-Ahiouy

区间求和与排序

题目描述

给定一个包含 n 个正整数的数组 a，你需要回答 t 个询问。每个询问给出两个整数 l 和 r，要求计算数组 a 在区间 [l, r] 内的元素之和，并让数组 [l, r] 部分从大到小排序，最后输出数组 a。

输入格式

第一行一个整数 n 。

第二行 n 个整数 a_i，用空格分隔。

第三行一个整数 t 。

接下来 t 行，每行两个整数 l_i, r_i，用空格分隔。

输出格式

每次查询返回区间 [l, r] 的和，并将数组 [l, r] 部分从大到小排序（排序不影响区间和，你可以想成两个数组，一个排序，一个求和），查询结束后最后返回数组 a （排序过的），用空格分隔。

输入输出样例

样例输入 #1

5
1 2 3 4 5
2
1 3
3 5[code]

[b]样例输出 #1[/b]

[code]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 解释】

第一行：为第一次询问，区间 [1, 3] 的和为6，并将数组 [1, 3] 区间进行降序排序。

第二行：为第二次询问，区间 [3, 5] 的和为12，并将数组 [3, 5] 区间进行降序排序。

第三行：查询结束，返回现在的数组。

数据范围

对于 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 10:55:48

排序不能优化，就懒得写前缀和了

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

int n, a[100001], t, l, r, b[100001];

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[i]);
                b[i] = a[i];
        }
        scanf("%d", &t);
        while (t--) {
                scanf("%d%d", &l, &r);
                long long sum = 0;
                for (int i = l; i <= r; ++i) sum += a[i];
                sort(b + l, b + r + 1, cmp);
                printf("%lld\n", sum);
        }
        for (int i = 1; i <= n; ++i) {
                printf("%d ", b[i]);
        }
    return 0;
}

跳转到最佳答案楼层

zhangjinxuan

排序不能优化，就懒得写前缀和了

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

int n, a[100001], t, l, r, b[100001];

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[i]);
                b[i] = a[i];
        }
        scanf("%d", &t);
        while (t--) {
                scanf("%d%d", &l, &r);
                long long sum = 0;
                for (int i = l; i <= r; ++i) sum += a[i];
                sort(b + l, b + r + 1, cmp);
                printf("%lld\n", sum);
        }
        for (int i = 1; i <= n; ++i) {
                printf("%d ", b[i]);
        }
    return 0;
}

Ewan-Ahiouy

@额外减小 @tommyyu @zhangjinxuan @sfqxx @isdkz @Mike_python小 @陈尚涵 来看看啊

zhangjinxuan

可以离线做欸，但是给区间离散化又麻烦

zhangjinxuan

cao，好像不能离线

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 10:59
可以离线做欸，但是给区间离散化又麻烦

想到什么地方去了？很基础的算法

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:02
想到什么地方去了？很基础的算法

查询一次做一次排序？

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:05
查询一次做一次排序？

你算算复杂度

sfqxx

哈哈，这不就是进阶篇那个前缀和啊

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:06
你算算复杂度

bushi，题目不是这么说的吗，查询一次做一次排序

Ewan-Ahiouy

sfqxx 发表于 2023-8-25 11:07
哈哈，这不就是进阶篇那个前缀和啊

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:05
查询一次做一次排序？

告诉你一个很好用的东西：氧气

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:07
告诉你一个很好用的东西：氧气

臭氧(╯▔皿▔)╯

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:08
臭氧(╯▔皿▔)╯

不是，你暴力？我的想法是前缀和来着不行，得加大强度

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:09
感觉 std 有点问题，因为 std 可能是最后再做一遍排序，而题目要求是查询了就要排序，感觉很奇怪。

气死我了！造数据怎么这么难！

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:09
感觉 std 有点问题，因为 std 可能是最后再做一遍排序，而题目要求是查询了就要排序，感觉很奇怪。

？

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:12
完了完了卧槽！丢脸丢尽了

想法只能暴力，因为时间复杂度瓶颈就在这个排序上

即使前缀和优化也不能优化排序

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:16
不是，为什么我要哭啊

不就是查询原数组的 l~r 吗？

如果真是这样的话就可以离线了

好像还是不能

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-25 11:18
如果真是这样的话就可以离线了

好像还是不能

就是求排序后的数组，查询排序前的区间

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-25 11:18
就是求排序后的数组，查询排序前的区间

那排序后的数组一定要 O(t n log n) 求解吗