问题分析

本题要求我们找到一个排列 p 中的所有“好数组”区间的个数。具体来说，给定一个排列 p 和多个查询，每个查询包含一个长度为奇数的区间 [l, r]，并要求判断区间内的中位数是否满足“好数组”的条件：该区间的中位数恰好是区间的第 (r - l + 1) // 2 + 1 的位置上的数字，并且此中位数在该区间内不需要进行排序后也符合中位数的定义。

“好数组”的定义

“好数组”要求数组的中位数即为该区间的第 (n + 1) / 2 个元素（即中间元素）。例如，若数组的长度为 5，那么第 3 个元素就是中位数。

解题思路

1. 中位数的定义： 对于一个长度为奇数的子数组，数组的中位数是该数组排序后位于中间位置的元素。例如，对于长度为 5 的子数组 p[l..r]，它的中位数就是 p[(l+r)//2]。

2. “好数组”区间的判断： 对于每个子区间，我们需要检查其是否是“好数组”。根据题目要求，找到所有长度为奇数的子数组，并且要判断这个子数组的中位数是否符合要求。

3. 解法思路： 我们从每一个元素出发，尝试扩大窗口，检查窗口内的中位数是否符合“好数组”的要求。具体步骤如下：

   • 对每一个可能的子数组，检查其是否为好数组。
   • 具体做法是对于每一个中位数，判断其是否满足条件，并用双指针的方式，计算所有符合条件的区间。

复杂度分析

• 两层循环，复杂度为$O(n^2)$

代码实现

Python代码实现

def solve():
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        p = list(map(int, input().split()))
        
        result = 0
        
        for i in range(n):
            d = 0
            total = 0
            for k in range(1, min(i, n -1 - i) + 1):
                left = i - k
                right = i + k
                
                total += 1 if p[left] > p[i] else -1
                total += 1 if p[right] > p[i] else -1
                
                if total == 0:
                    d += 1
            
            result += d + 1
        
        print(result)

# 输入调用
solve()

Java代码实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] p = new int[n + 1]; 
            st = new StringTokenizer(br.readLine());
            
            // 读取排列p
            for (int i = 1; i <= n; i++) {
                p[i] = Integer.parseInt(st.nextToken());
            }

            int rs = 0;
            
            // 计算每个位置作为中位数的子区间数量
            for (int i = 1; i <= n; i++) {
                int d = 0;
                int sum = 0;
                
                // 计算以i为中位数的子区间
                for (int k = 1; k <= Math.min(i-1, n - i); k++) {
                    int left = i - k;
                    int right = i + k;
                    
                    // 判断左右两侧元素是否符合“好数组”的条件
                    sum += (p[left] > p[i]) ? 1 : -1;
                    sum += (p[right] > p[i]) ? 1 : -1;
                    
                    // 如果当前区间满足条件，则计数
                    if (sum == 0) {
                        d++;
                    }
                }
                
                // 每个位置都要加1
                rs += d + 1;
            }
            
            // 输出每个测试的结果
            System.out.println(rs);
        }
    }
}

C++代码实现

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

void solve() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int d = 0;
            int total = 0;
            
            for (int k = 1; k <= min(i, n - i - 1); k++) {
                int left = i - k;
                int right = i + k;
                
                total += (p[left] > p[i]) ? 1 : -1;
                total += (p[right] > p[i]) ? 1 : -1;
                
                if (total == 0) {
                    d++;
                }
            }
            
            result += d + 1;
        }
        
        cout << result << endl;
    }
}

int main() {
    solve();
    return 0;
}

题目内容

众所周知，一个长度为$n$，$n$为奇数的数组的中位数是其排序后下标为$\frac{n+1}{2}$的数字。

但小美发现，有些长为奇数n的数组即使不排序，其下标为$\frac{n+1}{2}$的数字依然是其数组中位数，他将满足这样性质的数组成为“好数组"。

现在小美有一个长度为$n$的排列$p$，他想知道$p$中有多少个连续的区间组成的数组都是"好数组"。

(即有多少对$l,r(1≤l≤r≤n)$,同时$r-l+1$是奇数,满足$P_l,P_{l+1},··,P_r$是一个好数组。)

输入描述

每个测试文件内都包含多组测试数据。

第一行一个正整数$T(I≤T≤1000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行。

第一行两个整数$n(1≤n≤10000)$，表示排列$p$的长度。

第二行$n$个整数$p_i(1≤p_i≤n)$，表示排列$P$。

(保证输入是一个排列。)

(保证所有测试数据中$n$的总和不超过$10000$)

输出描述

输出包含 $T$行，每行一个正整数，表示合法的$l,r$对数。

样例1

输入

1
5
3 2 1 4 5

输出

7

说明

好数组的区间有: $[1, 1]$, $[2, 2]$, $[3,3]$, $[4,4]$, $[5,5]$, $[1, 3]$, $[3,5]$这 $7$个。