首页 > 试题广场 >

换个角度思考

[编程题]换个角度思考

热度指数：6 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数
即对于询问 (l,r,x)，你需要输出 $\sum_{i=l}^{r}[a_i \le x]$ 的值
其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式

输入描述:

第一行两个整数n,m
第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ a_i ≤ 10⁵
之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 10⁵

输出描述:

对于每一个询问，输出一个整数表示答案后回车

示例1

输入

5 1
1 2 3 4 5
1 5 3

输出

备注:

数据范围
1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10⁵

算法知识视频讲解

Kur1su

发表于 2020-05-06 20:28:16

太棒了, 学到了许多.jpg Solution 题意要求次区间查询小于等于的数有多少个, 区间问题首先就想到线段树/树状数组优先考虑树状数组(常数小, 写法简单), 但是我们做不到直接一边查询一边插入然后用求解因为原序列是无序的, 每次查询时, 都未知, 因此很难处理注意到问题给的区展开全文

青烟绕指柔

发表于 2020-04-29 11:33:53

显然是可以离线之后fenwick维护。因为不喜欢离线，所以直接主席树了。每次找到对应区间，然后相当于就是区间sum的问题了。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=N*40; i 展开全文

sunrise__sunrise

发表于 2020-04-29 16:19:01

Solution 直接模拟！！别问，问就是模拟，当然模拟的时间复杂度是O(m * n)居然没有超时。。算了先玄学A一发，贴代码。 Code #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_st 展开全文

shyyhs

发表于 2021-01-21 21:15:43

前言: 这题假如用树状数组的话,还是很不错的一个题的. 思路: 直接把两个序列都按权值排序,把查询的以及原序列,这样做的好处就是保证我插入的一定是合法的,然后直接查询即可. 代码: #include <bits/stdc++.h> using namespace std; const i 展开全文

wxyww

发表于 2020-04-29 11:45:28

solution 发现可以离线。将所有询问离线下来，按照查询的从小到大排序。并且将数组从小到大排序。按照从小到大的枚举每次询问，同时将所有的数字，将树状数组上位置。然后直接区间查询就行了。 code /* * @Author: wxyww * @Date: 2020-04-29 11:36:4 展开全文

苟且的狮子

发表于 2020-07-25 17:03:21

树状数组题意：分析：这两天一直在学习树状数组，但做题的时候总是有些摸不到头脑。不知道要在何处构造树状数组？又要用树状数组表示什么？通过这题，我来总结一下吧。这题中我们要求sum(l,r)[ai<=x]很明显直接去往区间里看是不行的，因为我们无法区分出ai<=x那我们简化一下问展开全文

流锡

发表于 2021-06-15 22:26:27

思路：看没人写莫队算法自己就写了一下写了一下发现和不同的莫队算法不一样普通的莫队算法不支持修改操作而这里因为询问的k会变你之前的区间的值都会受影响问了一下大佬结果学到了带修改莫队对于普通的莫队我们再加上一个变量t[a[x]]表示a[x]出现的次数再新增一个变量now，在每次询问中对于now<k 展开全文