二分搜索：给一个已经排好序的长度为nn的数组aa，第ii个元素是aiai​。 接下来有mm条询问，每个询问的格式为op xop x。如果op=1op=1,表示问xx第一次出现的位置是什么；如果op=2op=2，表示询问xx最后一次出现的位置是什么。如果xx从未出现过，输出Not Found。

你可以使用二分搜索来解决这个问题。首先，对于每个询问，你需要确定是要找第一次出现位置还是最后一次出现位置。

对于第一次出现位置的查询，你可以使用经典的二分搜索算法来找到第一个等于xx的元素。具体步骤如下：

1. 初始化左指针ll为0，右指针rr为nn-1。
2. 当ll <= rr时，重复以下步骤：
a. 计算中间位置mm为 (ll + rr) / 2。
b. 如果a[m] < xa[m] < x，则更新ll = m + 1。
c. 如果a[m] > xa[m] > x，则更新rr = m - 1。
d. 如果a[m] = xa[m] = x，则说明找到了第一次出现的位置，返回mm。
3. 如果循环结束仍然没有找到等于xx的元素，则返回"Not Found"。

对于最后一次出现位置的查询，你可以做一个类似的修改。具体步骤如下：

1. 初始化左指针ll为0，右指针rr为nn-1。
2. 当ll <= rr时，重复以下步骤：
a. 计算中间位置mm为 (ll + rr) / 2。
b. 如果a[m] < xa[m] < x，则更新ll = m + 1。
c. 如果a[m] > xa[m] > x，则更新rr = m - 1。
d. 如果a[m] = xa[m] = x，则说明找到了最后一次出现的位置，更新ll = m + 1，继续搜索。
3. 如果循环结束仍然没有找到等于xx的元素，则返回"Not Found"。

通过以上步骤，你可以使用二分搜索算法来解决这个问题。记得对每个询问进行相应的操作，并输出结果。

相关问题

这道题 输入 nn 个不大于 105105 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。 输入格式 第一行输入一个正整数 nn，表示整数个数。 第二行输入 nn 个正整数 aiai​，以空格隔开。 输出格式 输出一行，依次输出 aiai​ 中剩余的质数，以空格隔开。 我的代码为什么错了一个#include<bits/stdc++.h> using namespace std; bool zs(int c) { bool a=1; for(int i=2;i<=sqrt(c);i++) { if(c%i==0) a=0; } return a; } int main() { int a[100001],b; scanf("%d",&b); for(int i=0;i<b;i++) { scanf("%d",&a[i]); int c=a[i]; if(zs(c)) printf("%d ",a[i]); } return 0; }

你的代码中，只输出了质数，但是没有去除非质数的数字。你需要在输入数字的同时，进行判断是否为质数，并将质数存入数组中，最后再输出数组中的质数。可以参考下面的代码：

#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int a[n], cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (is_prime(a[i])) {
            cnt++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (is_prime(a[i])) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

用c++实现：Jimmy 作为一名 SCUT 的大学生，自然需要去学习。 在 SCUT，Jimmy 的课表上有 N 门不同的课程，在学期的每一周内他总共会上 N 次课，每一门课程恰好一周上一次课，Jimmy 对于每一个课程都有一个熟练度，初始时都为 0。 对于一节课 Jimmy 可以选择如下两种选项之一： 1. 去上课：如果 Jimmy 选择去上课，此时他对于这节课的熟练度增加 AiAi​。 2. 翘课：Jimmy 热爱学习，因此他会在翘课的时候找地方自学，此时他对于这节课的熟练度增加 BiBi​。 为了去学习更多的课外知识，Jimmy 不会在其余时间学习这 N 门课程，但是他又不想要让自己的成绩排名靠后，于是他找到了你，请你帮忙让他在每周恰好翘 k 门课时，他所有课程熟练度总和尽可能大。 输入格式 第一行两个整数 N, k 接下来一行 N 个整数 AiAi​。 接下来一行 N 个整数 BiBi​。 输出格式 仅输出一行一个整数，表示 Jimmy 在每周恰好翘 k 门课时所有课程熟练度总和的最大值，内存限制256MB，时间限制2s

好的，下面是用 C++ 实现的代码，采用二维动态规划思想：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5010;

int n, k;
int a[N], b[N];
int f[N][N];

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

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= k; j ++ )
        {
            // 不翘课
            f[i][j] = max(f[i][j], f[i - 1][j] + a[i] + b[i]);

            // 翘课
            if (j) f[i][j] = max(f[i][j], f[i - 1][j - 1] + b[i]);
        }

    int res = -1e9;
    for (int i = 0; i <= k; i ++ )
        res = max(res, f[n][i]);

    cout << res << endl;

    return 0;
}

具体思路如下：

1. 定义 $f[i][j]$ 表示前 $i$ 门课，翘了 $j$ 门课时，所有课程熟练度总和的最大值。

2. 初始化 $f[0][0] = 0$。

3. 对于每一门课，有两种选择：

- 选择上课，则 $f[i][j] = f[i-1][j] + a[i] + b[i]$。

- 选择翘课，则 $f[i][j] = f[i-1][j-1] + b[i]$。

4. 最终答案为 $\max\limits_{i=0}^k f[n][i]$。

时间复杂度为 $O(nk)$，空间复杂度为 $O(nk)$。