{"trustable":false,"sections":[{"title":"Background","value":{"format":"MD","content":"这是一道 ST 表经典题——静态区间最大值\n\n**请注意最大数据时限只有 $0.8$ 秒,数据强度不低,请务必保证你的每次查询复杂度为 $O(1)$。若使用更高时间复杂度算法不保证能通过。**\n\n如果您认为您的代码时间复杂度正确但是 TLE,可以尝试使用快速读入:\n\n```cpp\ninline int read()\n{\n\tint x\u003d0,f\u003d1;char ch\u003dgetchar();\n\twhile (ch\u003c\u00270\u0027||ch\u003e\u00279\u0027){if (ch\u003d\u003d\u0027-\u0027) f\u003d-1;ch\u003dgetchar();}\n\twhile (ch\u003e\u003d\u00270\u0027\u0026\u0026ch\u003c\u003d\u00279\u0027){x\u003dx*10+ch-48;ch\u003dgetchar();}\n\treturn x*f;\n}\n```\n\n函数返回值为读入的第一个整数。\n\n**快速读入作用仅为加快读入,并非强制使用。**"}},{"title":"Description","value":{"format":"MD","content":"给定一个长度为 $N$ 的数列,和 $ M $ 次询问,求出每一次询问的区间内数字的最大值。\n"}},{"title":"Input","value":{"format":"MD","content":"第一行包含两个整数 $N,M$,分别表示数列的长度和询问的个数。\n\n第二行包含 $N$ 个整数(记为 $a_i$),依次表示数列的第 $i$ 项。\n\n接下来 $M$ 行,每行包含两个整数 $l_i,r_i$,表示查询的区间为 $[l_i,r_i]$。"}},{"title":"Output","value":{"format":"MD","content":"输出包含 $M$ 行,每行一个整数,依次表示每一次询问的结果。\n"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 8\n9 3 1 7 5 6 0 8\n1 6\n1 5\n2 7\n2 6\n1 8\n4 8\n3 7\n1 8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n9\n7\n7\n9\n8\n7\n9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Constraints","value":{"format":"MD","content":"- 对于 $30\\%$ 的数据,满足 $1\\le N,M\\le 10$。\n- 对于 $70\\%$ 的数据,满足 $1\\le N,M\\le {10}^5$。\n- 对于 $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$。"}}]}