首页 > 试题广场 >

序列维护

[编程题]序列维护

小易在维护数据的时候遇到一个需求，具体来说小易有一系列数据，这些数据了构成一个长度为n的数字序列，接下来小易会在这个序列上进行q次操作。
每次操作有一个查询的数字x，小易需要将序列数据中所有大于等于x的数字都减一，并输出在本次操作中有多少个数字被减一了。
小易犯了难，希望你能帮帮他。

第一行n,q，表示数字个数和操作个数。 
接下来一行n个数表示初始的数字。 
接下来q行，每行一个数，表示指定的数字x。
，

对于每个询问，输出一个数字表示答案

示例1

输入

1
2
4

示例2

1
0

算法知识视频讲解

永远鲜红的幼月

发表于 2020-04-06 16:38:19

一个板子题.不过看评论那么多O(n^2)的解法...反正我用O(n^2)试了试..没过... 其实二分套线段树还挺常见的. 不过因为长时间没写过题了..我线段树板子都快忘了,花了一个多小时才回忆起来... 下面是思路: 由于是将所有>=x的数减一.所以我们很容易想到线段展开全文

freezerhan

发表于 2020-09-12 13:48:35

#include <bits/stdc++.h> using namespace std; class segtree{ public: int n; int* data; int* tree; int* lazy; segtree(int* arr, int 展开全文

C++工程师安卓工程师前端工程师网易算法工程师测试工程师 2020 数据分析师 Java工程师

上传者：小小

难度：

50条回答 203收藏 8067浏览

扫一扫，把题目装进口袋