琴

GitHub跳转原题关系图返回列表

值域只有 1~50，排序后相邻差 ≤1 等价于难度值连续不断档，答案是从区间最小难度到第一个空档的出现次数之和。

OJ: roj

题目 ID: 20023

难度:普及-

标签:前缀和桶区间

创建: 2026-08-29 00:08

更新: 2026-10-07 13:50

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定长度为 nn 的序列 aia_i（1≤ai≤501\le a_i\le 50）。mm 次询问，每次给出区间 [l,r][l,r]：把区间内的数从小到大排序，从第一个数开始向后走，要求相邻两数差为 00 或 11，否则停止。输出每天实际练习的曲目数。

输入：nn、序列、mm，以及 mm 组 li,ril_i,r_i。输出：mm 行答案。数据范围 n,m≤105n,m\le 10^5。

思路

排序后相邻差 ≤1\le 1 等价于从区间最小难度起连续不断档。对每个难度值 1∼501\sim50 建前缀和，每次询问先找最小出现难度，再累加直到第一个出现次数为 00 的难度。复杂度 O((n+m)⋅50)O((n+m)\cdot 50)。

参考代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:40
 * update_at: 2026-10-06 09:13
 */
// main.cpp：T3 琴(instrument) 最终解。
// 值域只有 1..50，对每个难度值 v 开一个前缀和数组，
// 每次询问从区间内出现的最小难度 mn 开始累加出现次数，遇到断档(次数为 0)就停止。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 50;

int n, m;
int a[MAXN];
// pre[v][i]：前 i 个位置中难度值恰好为 v 的曲目数量
int pre[MAXV + 1][MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 预处理：每个难度值一个前缀和数组，O(n * V)
    for (int v = 1; v <= MAXV; v++) {
        for (int i = 1; i <= n; i++) {
            pre[v][i] = pre[v][i - 1] + (a[i] == v);
        }
    }

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;

        // 第一步：找区间内出现的最小难度 mn
        int mn = 0;
        for (int v = 1; v <= MAXV; v++) {
            if (pre[v][r] - pre[v][l - 1] > 0) {
                mn = v;
                break;
            }
        }

        // 第二步：从 mn 开始累加各难度出现次数，遇到第一个断档(出现次数为 0)就停
        int total = 0;
        for (int v = mn; v <= MAXV; v++) {
            int cnt = pre[v][r] - pre[v][l - 1];
            if (cnt == 0) break;
            total += cnt;
        }
        cout << total << '\n';
    }

    return 0;
}