前言

简介：涉及ST表，题目源于洛谷
建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。

所谓ST表。

详细了解可至链接：OI-wiki ST 表

模板题

洛谷P3865 【模板】ST 表

题目链接： P3865 【模板】ST 表

题目描述
【模板】ST 表
题目背景
这是一道 ST 表经典题——静态区间最大值

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O(1)$。若使用更高时间复杂度算法不保证能通过。
如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

函数返回值为读入的第一个整数。
快速读入作用仅为加快读入，并非强制使用。
题目描述
给定一个长度为 $N$ 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 $N,M$，分别表示数列的长度和询问的个数。
第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。
接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$。
输出格式
输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。
样例 #1
样例输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

样例输出 #1

9
9
7
7
9
8
7
9

提示
对于 $30\%$ 的数据，满足 $1\le N,M\le 10$。
对于 $70\%$ 的数据，满足 $1\le N,M\le {10}^5$。
对于 $100\%$ 的数据，满足 $1\le N\le {10}^5$，$1\le M\le 2\times{10}^6$，$a_i\in[0,{10}^9]$，$1\le l_i\le r_i\le N$。

ac题解

//时间:1.04s(O2:992ms)  内存:8.09MB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 405
int n,m;
int st[100005][20];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
} 

int find(int l,int r){
    int t=log2(r-l+1);
    return max(st[l][t],st[r+1-(1<<t)][t]);
}
int main()
{
    int i,j;
    n=read();
    m=read();
    for(i=1;i<=n;i++) st[i][0] = read();
    for(i=1;(1<<i)<=n;i++)
        for(j=1;(j-1+(1<<i))<=n;j++)
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);

    while(m--){
        i=read();
        j=read();
        printf("%d\n",find(i,j));
    }
    return 0;    
}

P8773 [蓝桥杯 2022 省 A] 选数异或

题目链接：P8773 [蓝桥杯 2022 省 A] 选数异或

题目描述
给定一个长度为 $n$ 的数列 $A{1}, A{2}, \cdots, A{n}$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l, r]$ 中选择两个数使得他们的异或等于 $x$ 。
输入格式
输入的第一行包含三个整数 $n, m, x$ 。
第二行包含 $n$ 个整数 $A{1}, A{2}, \cdots, A{n}$。
接下来 $m$ 行，每行包含两个整数 $l{i}, r{i}$ 表示询问区间 $\left[l{i}, r{i}\right]$ 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 $x$ 则输出 yes, 否则输出 no。
样例 #1
样例输入 #1

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

样例输出 #1

yes
no
yes
no

提示
【样例说明】
显然整个数列中只有 2,3 的异或为 1 。
【评测用例规模与约定】
对于 $20 \%$ 的评测用例, $1 \leq n, m \leq 100$;
对于 $40 \%$ 的评测用例, $1 \leq n, m \leq 1000$;
对于所有评测用例, $1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1="" \leq="" l_{i}="" r_{i}="" n$="" ，="" $0="" a_{i}<2^{20}$="" 。 蓝桥杯 2022 省赛 A 组 D 题。

ac题解