数组查询给出错误答案

Question

我有一个问题，我不知道如何开始，这里是：

You are given a permutation of 1,2,...,n. You will be given q queries, each query being one of 2 types:

Type 1: swap elements at positions i and j
Type 2: given a position i, print the length of the longest subarray containing the ith element such that the sum of its elements doesn't exceed n

Input

The first line contains 2 integers n and q (1≤n,q≤105).

The next line contains the n integers of the permutation p1,…,pn (1≤pi≤n).

The next q lines contain queries in the format:

Type 1: 1 i j (1≤i,j≤n)
Type 2: 2 i (1≤i≤n)

Output

For each query of type 2, print the required answer.

到目前为止，这是我的代码，但它在最后几种情况下给出了错误的答案：

#include <iostream>
#include <algorithm>

long long atMostSum(int arr[], int n, int k, int a)
{
    int sum = arr[a];
    int cnt = 1, maxcnt = 1;

    for (int i = 0; i < n; i++) {

        if ((sum + arr[i]) <= k) {
            sum += arr[i];
            cnt++;
        }

        else if(sum!=0)
        {
            sum = sum - arr[i - cnt] + arr[i];
        }

        maxcnt = std::max(cnt, maxcnt);
    }
    return maxcnt - 1;
}

int main(void) {
    int n, q;
    std::cin >> n >> q;
    int p[n];
    for(int i = 0; i < n ; i++) {
        std::cin >> p[i];
    }
    for (int i = 0; i < n; i ++) {
        int a;
        std::cin >> a;
        if (a == 2) {
            int m;
            std::cin >> m;
            std::cout << atMostSum(p, n, n, m) << "\n";
        } else {
            int l, f;
            std::cin >> l >> f;
            int temp;
            temp = p[l];
            p[l] = p[f];
            p[f] = temp;
        }
    }
}

示例输入

示例输出

2
2
1

Answer 1

无法为您提供完整的解决方案，但可以帮助您入门。您基本上是在 arr[1...n] 中寻找一个子集，它由元素 arr[i] 和不超过 n 的总和组成。所以简单地寻找一个总和为 (n - arr[i]) 的子数组，然后它就变成了寻找 子数组的经典问题给定总和

您可以在这里参考后面的解决方案 - https://www.geeksforgeeks.org/find-subarray-with-given-sum/

Answer 2

long long atMostSum(int arr[], int n, int k, int a){
    long long ans = arr[a];

    for (int i = 0; i <= a; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if(sum > n) break;
            if(i <= a && a <= j) {
               ans = max(ans, sum);
            }
        }
    }
    return ans;
}

这对于复杂性来说不是最好的，但应该是正确的...

数组查询给出错误答案

Array queries give wrong answer

c++

arrays

permutation

Input

Output

示例输入

示例输出