题目分析

题意简述

给定一个包含 $N$（$1 < N \leq 50000$ 且 $N$ 为偶数）个整数的数组 $A$，数组 $A$ 的元素由公式 $A[i] = (a_1 \times i \times i + a_2 \times i + a_3) \bmod 9973$ 确定，其中 $1 \leq a_i \leq 50000$（$i = 1, 2, 3$）。另外有三个数组 $S$、$E$ 和 $R$，数组 $S$ 和 $E$ 各有 $M$（$1 \leq M \leq 50000$）个元素，$S[i] = (s_1 \times i \times i + s_2 \times i + s_3) \bmod (N/2)$，$E[i] = S[i] + [(e_1 \times i \times i + e_2 \times i + e_3) \bmod (N/2)]$，其中 $1 \leq s_i, e_i \leq 50000$（$i = 1, 2, 3$）。而 $R[i] = \min\{A[S[i]], A[S[i] + 1], \cdots, A[E[i]]\}$。需要找出最小的 $j$，使得 $R[j] = \max\{R[0], R[1], \cdots, R[M - 1]\}$。

输入

• 第一行输入测试用例的数量 $t$。
• 对于每个测试用例，输入一行包含 $11$ 个整数，分别为 $N$、$a_1$、$a_2$、$a_3$、$M$、$s_1$、$s_2$、$s_3$、$e_1$、$e_2$、$e_3$。

输出

对于每个测试用例，输出一行，为满足 $R[j] = \max\{R[0], R[1], \cdots, R[M - 1]\}$ 的最小的 $j$ 值。

解题思路

构建线段树

为了高效地查询数组 $A$ 中任意区间 $[S[i], E[i]]$ 的最小值，使用线段树这种数据结构。通过递归构建线段树，每个节点存储对应区间的最小值。

计算 $S$、$E$ 和 $R$ 数组

• 根据给定的公式计算数组 $S$ 和 $E$ 的每个元素。
• 利用线段树查询 $A$ 数组中 $[S[i], E[i]]$ 区间的最小值，得到 $R$ 数组的每个元素。

找出最大 $R$ 值的最小索引

遍历 $R$ 数组，找出最大值，并记录该最大值第一次出现的索引。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

int N, M;
int a1, a2, a3, s1, s2, s3, e1, e2, e3;

int xds[200002];

int mum[50005];

int S(long long int i){
    long long int ans = i*i*s1 + i*s2 + s3;
    return (int)(ans%(N/2));
}

int E(long long int i, int s){
    long long int ans = i*i*e1 + i*e2 + e3;
    return s + (int)(ans%(N/2));
}

int A(long long int i){
    long long int ans = i*i*a1 + i*a2 + a3;
    return (int)(ans%9973);
}

int mn(int a, int b){
    return (a<b) ? a : b;
}

void jxds(int start, int end, int bh){
    if(start == end){
        xds[bh] = A(start);
        return;
    }
    int mid = (start+end)/2;
    jxds(start, mid, 2*bh+1);
    jxds(mid+1, end, 2*bh+2);
    xds[bh] = mn(xds[2*bh+1], xds[2*bh+2]);
}

int cx(int cxStart, int cxEnd, int xzStart, int xzEnd, int bh){
    if(cxStart == xzStart && cxEnd == xzEnd){
        return xds[bh];
    }
    int xzMid = (xzStart+xzEnd)/2;
    if(cxEnd <= xzMid){
        return cx(cxStart, cxEnd, xzStart, xzMid, 2*bh+1);
    }
    else if(cxStart > xzMid){
        return cx(cxStart, cxEnd, xzMid+1, xzEnd, 2*bh+2);
    }
    else{
        int hx1 = cx(cxStart, xzMid, xzStart, xzMid, 2*bh+1);
        int hx2 = cx(xzMid+1, cxEnd, xzMid+1, xzEnd, 2*bh+2);
        return mn(hx1, hx2);
    }
}

int cx(int s, int e){
    return cx(s, e, 0, N-1, 0);
}

int main() {
    int t;
    scanf("%d", &t);
    for(int ii = 0; ii < t; ii++){
        scanf("%d%d%d%d%d%d%d%d%d%d%d", &N , &a1, &a2, &a3, &M ,&s1, &s2, &s3, &e1, &e2, &e3);
        jxds(0, N-1, 0);
        int mx = 0;
        for(int i = 0; i < M; i++){
            int si = S(i);
            int ei = E(i, si);
            mum[i] = cx(si, ei);
            //cout << mum[i] << endl;
            if(mum[i] > mx) mx = mum[i];
        }
        for(int i = 0; i < M; i++){
            if(mum[i] == mx){
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

代码说明

1. 全局变量：
   • N 和 M 分别存储数组 $A$ 的长度和数组 $S$、$E$、$R$ 的长度。
   • a1、a2、a3、s1、s2、s3、e1、e2、e3 存储输入的系数。
   • xds 数组用于存储线段树的节点值。
   • mum 数组用于存储 $R$ 数组的元素。
2. 函数功能：
   • S(i)：根据公式计算 $S[i]$ 的值。
   • E(i, s)：根据公式计算 $E[i]$ 的值，其中 s 为 $S[i]$ 的值。
   • A(i)：根据公式计算 $A[i]$ 的值。
   • mn(a, b)：返回 $a$ 和 $b$ 中的较小值。
   • jxds(start, end, bh)：递归构建线段树，start 和 end 表示当前节点对应的区间，bh 表示当前节点在线段树数组中的编号。
   • cx(cxStart, cxEnd, xzStart, xzEnd, bh)：在线段树中查询区间 $[cxStart, cxEnd]$ 的最小值，xzStart 和 xzEnd 表示当前节点对应的区间，bh 表示当前节点在线段树数组中的编号。
   • cx(s, e)：调用 cx(cxStart, cxEnd, xzStart, xzEnd, bh) 函数查询区间 $[s, e]$ 的最小值。
3. 主函数流程：
   • 读取测试用例的数量 $t$。
   • 对于每个测试用例：
     • 读取 $N$、$a_1$、$a_2$、$a_3$、$M$、$s_1$、$s_2$、$s_3$、$e_1$、$e_2$、$e_3$。
     • 调用 jxds(0, N - 1, 0) 构建线段树。
     • 遍历 $i$ 从 $0$ 到 $M - 1$，计算 $S[i]$ 和 $E[i]$，并使用线段树查询 $A$ 数组中 $[S[i], E[i]]$ 区间的最小值，存储在 mum[i] 中，同时更新最大值 mx。
     • 再次遍历 $i$ 从 $0$ 到 $M - 1$，找到第一个满足 mum[i] == mx 的 $i$，输出该 $i$ 值。