C++信奥教学PPT：CSP_S _基础算法之离散算法

一枚大果壳

发布于 2024-04-17 13:43:20

800

发布于 2024-04-17 13:43:20

文章被收录于专栏：编程驿站编程驿站

声明：此系列PPT章节内容遵循全国青少年信奥赛大纲的要求组织、制作。PPT中的内容主要来源于个人公众号发布的技术性文章。PPT中也收集了不少刷题网站上的试题。

数列离散化

题目描述

给定一个长度为

的数列

。定义

\mathrm{rank}(i)

表示数列

中比

a_i

小的不同数字个数再加一。

对

1 \leq i \leq n

，现在请你求出所有的

\mathrm{rank}(i)

。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数，表示数据组数

。接下来依次给出每组数据的信息：

第一行是一个整数，表示数列长度

。第二行有

个整数表示数列

，第

个整数表示

a_i

。

输出格式

对每组数据，输出一行

个整数，用空格隔开，依次表示

\mathrm{rank}(1)

到

\mathrm{rank}(n)

。

样例 #1

样例输入 #1

3
3
1 2 3
5
1 6 2 2 7
4
-1 -2 -3 -3

样例输出 #1

1 2 3
1 3 2 2 4
3 2 1 1

提示

数据规模与约定

对全部的测试点，保证

1 \leq T \leq 5

，

1 \leq n \leq 10^5

，

-10^9 \leq a_i \leq 10^9

。

可持久化线段树

题目背景

这是个非常经典的可持久化权值线段树入门题——静态区间第

小。

数据已经过加强，请使用可持久化权值线段树。同时请注意常数优化。

题目描述

如题，给定

个整数构成的序列

，将对于指定的闭区间

[l, r]

查询其区间内的第

小值。

输入格式

第一行包含两个整数，分别表示序列的长度

和查询的个数

。第二行包含

个整数，第

个整数表示序列的第

个元素

a_i

。接下来

行每行包含三个整数

l, r, k

, 表示查询区间

[l, r]

内的第

小值。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

样例输出 #1

提示

样例 1 解释

n=5

，数列长度为

，数列从第一项开始依次为

\{25957, 6405, 15770, 26287, 26465\}

。

第一次查询为

[2, 2]

区间内的第一小值，即为

6405

。

第二次查询为

[3, 4]

区间内的第一小值，即为

15770

。

第三次查询为

[4, 5]

区间内的第一小值，即为

26287

。

第四次查询为

[1, 2]

区间内的第二小值，即为

25957

。

第五次查询为

[4, 4]

区间内的第一小值，即为

26287

。

数据规模与约定

对于

20\%

的数据，满足

1 \leq n,m \leq 10

。

对于

50\%

的数据，满足

1 \leq n,m \leq 10^3

。

对于

80\%

的数据，满足

1 \leq n,m \leq 10^5

。

对于

100\%

的数据，满足

1 \leq n,m \leq 2\times 10^5

，

|a_i| \leq 10^9

，

1 \leq l \leq r \leq n

，

1 \leq k \leq r - l + 1

。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自编程驿站微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度