题目 小蚂蚁吃米 连续自然数和 差分 语文成绩 买凤梨
小蚂蚁吃米
题目大意
有一个长度为 nnn 的数组,表示小蚂蚁每天吃的白大米数量。现在有 qqq 次查询,每次查询给出区间 [L,R][L, R][L,R],要求输出小蚂蚁这段时间内吃的大米总数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 需要多次快速求数组区间和。
* 由于 n,qn, qn,q 可以较大,使用前缀和数组预处理。
* 查询复杂度可以降到 O(1)O(1)O(1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 预处理前缀和数组 preprepre,其中
pre[i]=a1+a2+⋯+aipre[i] = a_1 + a_2 + \cdots + a_ipre[i]=a1 +a2 +⋯+ai
1. 对于查询 [L,R][L, R][L,R],结果为
pre[R]−pre[L−1]pre[R] - pre[L-1]pre[R]−pre[L−1]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
连续自然数和
题目描述
给定一个正整数 MMM,找出所有连续正整数区间,区间长度至少为2,且区间内所有数之和等于 MMM。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
输入格式
一个整数 MMM。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
输出格式
按起始数字从小到大,输出所有满足条件的区间,每行两个整数,表示起始数和结束数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 利用前缀和数组快速计算区间和;
* 枚举左端点 lll,对每个 lll 从 l+1l+1l+1 开始枚举右端点 rrr;
* 当区间和等于 MMM 输出结果;
* 当区间和超过 MMM 立即跳出该轮循环(剪枝)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
差分
题目描述
给定一个长度为 nnn 的整数序列,进行 mmm 次区间加法操作,每次操作给区间 [l,r][l, r][l,r] 上的所有元素加上一个整数 ccc。最后输出操作后的序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
利用差分数组可以将区间加法的操作转化为两端点的加减操作,从而实现 O(1)O(1)O(1) 时间内完成区间修改,最后再根据差分数组恢复出最终序列。
具体步骤:
1. 初始化差分数组 ddd,长度为 nnn:
d[1]=a1,d[i]=ai−ai−1(2≤i≤n)d[1] = a_1, \quad d[i] = a_i - a_{i-1} \quad (2 \le i \le n)d[1]=a1 ,d[i]=ai −ai−1 (2≤i≤n)
2. 对于每个操作 [l,r,c][l, r, c][l,r,c]:
d[l]+=cd[l] += cd[l]+=c
如果 r+1≤nr+1 \le nr+1≤n,则:
d[r+1]−=cd[r+1] -= cd[r+1]−=c
3. 对差分数组做前缀和还原序列:
ai=∑k=1id[k]a_i = \sum_{k=1}^i d[k]ai =∑k=1i d[k]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码示范
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
语文成绩
题目大意
有 nnn 个学生,给出每个学生的初始语文成绩。老师将对多个区间进行加分操作,每次给第 xxx 到第 yyy 个学生的成绩都加上 zzz 分。你需要输出所有操作完成后,全班学生的最低分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个典型的 区间加法操作 问题,使用朴素做法每次遍历 [x,y][x, y][x,y] 区间将会导致 O(pn)O(pn)O(pn) 的复杂度,显然超时。可以使用 差分数组 优化为 O(n+p)O(n + p)O(n+p) 时间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
设数组 aaa 表示成绩数组,差分数组 ddd 定义为:
* d[1]=a[1]d[1] = a[1]d[1]=a[1]
* d[i]=a[i]−a[i−1](2≤i≤n)d[i] = a[i] - a[i - 1] \quad (2 \le i \le n)d[i]=a[i]−a[i−1](2≤i≤n)
对于区间加法 [x,y][x, y][x,y] 加 zzz,只需:
* d[x]+=zd[x] += zd[x]+=z
* d[y+1]−=zd[y + 1] -= zd[y+1]−=z
操作完后,再通过前缀和还原原数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 构造差分数组:O(n)O(n)O(n)
* 处理 ppp 次加法操作:O(p)O(p)O(p)
* 还原数组并找最小值:O(n)O(n)O(n)
总时间复杂度为:O(n+p)O(n + p)O(n+p),完全可以应对 n,p≤5×105n, p \leq 5 \times 10^5n,p≤5×105 的数据范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
买凤梨
题目大意
你有 nnn 本美食书,每本书推荐了一个甜度区间 [l,r][l, r][l,r]。
如果一个甜度被 不少于 kkk 本书推荐,则这个甜度是“合适”的。
现在有 qqq 次询问,每次询问一个区间 [l,r][l, r][l,r],你需要回答这个区间中有多少个“合适”的甜度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 本质上是区间统计问题。
* 每本书推荐了一个甜度区间 → 相当于这个区间里的每一个甜度值 xxx 被推荐了一次。
* 若一个甜度值 xxx 被推荐的次数 ≥k\ge k≥k,则称它是合适甜度。
我们需要支持:
* 快速判断一个甜度是否合适;
* 快速查询某一甜度区间中有多少个甜度是合适的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用 差分数组 + 前缀和优化:
1. 使用差分数组 a[i],对每个推荐区间 [l,r][l, r][l,r]:
* a[l]+=1a[l] += 1a[l]+=1
* a[r+1]−=1a[r+1] -= 1a[r+1]−=1
2. 遍历一遍求前缀和 a[i]a[i]a[i],得到每个甜度值被推荐了多少次。
3. 另设一个数组 ok[i],如果 a[i]≥ka[i] \ge ka[i]≥k,则令 ok[i] = 1,否则为 000。
4. 再对 ok[i] 求前缀和。
5. 对于每次询问 [l,r][l, r][l,r],答案就是 ok[r] - ok[l-1]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 差分与前缀和:O(MAX)O(\text{MAX})O(MAX),其中 MAX=2×105\text{MAX} = 2 \times 10^5MAX=2×105
* 每次询问时间复杂度:O(1)O(1)O(1),共 qqq 次,总代价 O(q)O(q)O(q)
* 总时间复杂度:O(n+MAX+q)=O(2×105)O(n + \text{MAX} + q) = O(2 \times 10^5)O(n+MAX+q)=O(2×105) 级别
可以应对所有数据范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现