Ewan-Ahiouy 发表于 2023-8-25 10:55:47

每日一题【#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 10:55:48

本帖最后由 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;
}

Ewan-Ahiouy 发表于 2023-8-25 10:58:16

@额外减小 @tommyyu @zhangjinxuan @sfqxx @isdkz @Mike_python小 @陈尚涵 来看看啊{:10_256:}

zhangjinxuan 发表于 2023-8-25 10:59:49

可以离线做欸,但是给区间离散化又麻烦{:10_277:}

zhangjinxuan 发表于 2023-8-25 11:01:26

cao,好像不能离线

Ewan-Ahiouy 发表于 2023-8-25 11:02:12

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

想到什么地方去了?{:10_277:}很基础的算法{:10_277:}

zhangjinxuan 发表于 2023-8-25 11:05:14

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

查询一次做一次排序?

Ewan-Ahiouy 发表于 2023-8-25 11:06:21

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

你算算复杂度

sfqxx 发表于 2023-8-25 11:07:00

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

zhangjinxuan 发表于 2023-8-25 11:07:12

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

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

Ewan-Ahiouy 发表于 2023-8-25 11:07:13

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

{:10_256:}

Ewan-Ahiouy 发表于 2023-8-25 11:07:33

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

告诉你一个很好用的东西:氧气{:10_327:}

zhangjinxuan 发表于 2023-8-25 11:08:06

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

臭氧(╯▔皿▔)╯

Ewan-Ahiouy 发表于 2023-8-25 11:09:17

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

不是,你暴力?我的想法是前缀和来着{:10_257:}不行,得加大强度{:10_244:}

Ewan-Ahiouy 发表于 2023-8-25 11:10:30

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

气死我了!造数据怎么这么难!{:10_244:}

Ewan-Ahiouy 发表于 2023-8-25 11:11:03

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

zhangjinxuan 发表于 2023-8-25 11:13:20

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

想法只能暴力,因为时间复杂度瓶颈就在这个排序上{:10_266:}

即使前缀和优化也不能优化排序{:10_266:}

zhangjinxuan 发表于 2023-8-25 11:18:03

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

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


如果真是这样的话就可以离线了{:10_257:}

好像还是不能

Ewan-Ahiouy 发表于 2023-8-25 11:18:49

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

好像还是不能

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

zhangjinxuan 发表于 2023-8-25 11:19:25

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

那排序后的数组一定要 O(t n log n) 求解吗{:10_272:}
页: [1] 2
查看完整版本: 每日一题【#1】