#556. 【2024-11-24 P2】中位数问题

【2024-11-24 P2】中位数问题

题目描述

给定一个长度为 nn 的排列 p=[p1,p2,…pn]p = [p_1, p_2, \dots p_n],对于所有的整数 xx 满足 1≤x≤n1 \leq x \leq n,你要确定:是否存在一个长度为奇数且不为 11 的区间 [l,r][l, r],使得 xx 是 pl,pl+1,…pr−1,prp_l, p_{l + 1}, \dots p_{r - 1}, p_r 的中位数。

输入格式

本题单个测试点内有多组测试数据。第一行是一个整数 TT,表示数据组数。对每组数据,按如下格式读入:

第一行是一个整数,表示排列的长度 nn。
第二行是 nn 个整数,表示这个排列 pp。

输出格式

对于每组数据,输出一行一个长度为 nn 的字符串。如果对 xx 存在符合要求的区间,则 ss 的第 xx 个字符是 y\mathrm{y},否则 ss 的第 xx 个字符是 n\mathrm{n}。

样例

样例输入 1

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

样例输出 1

nyynn
nyn
nyyyn

输入输出样例 2

见选手目录下的 /medium/medium2.in 和 /medium/medium2.ans。

输入输出样例 3

见选手目录下的 /medium/medium3.in 和 /medium/medium3.ans。

这个样例满足特殊性质 B。

输入输出样例 4

见选手目录下的 /medium/medium4.in 和 /medium/medium4.ans。

这个样例满足特殊性质 C。

数据范围与提示

我们用 NN 表示单个测试点内 nn 之和,则数据范围满足如下约定:

测试点编号 NN 特殊性质
1,21,2 ≤960\leq 960 A
3,43,4 ≤5000\leq 5000 无
5,65, 6 ≤106\leq 10^6 B
7,87,8 C
9,109,10 无
  • 特殊性质 A:n≤8n \leq 8。
  • 特殊性质 B:对每组数据,至多存在 100100 个 i∈[2,n−1]i \in [2, n-1],满足 (pi−pi−1)(pi+1−pi)<0(p_{i} - p_{i - 1})(p_{i + 1} - p_{i}) < 0。
  • 特殊性质 C:测试点内的全部数据总共存在至多 40004000 个 i∈[2,n−1]i \in [2, n-1],满足 (pi−pi−1)(pi+1−pi)<0(p_{i} - p_{i - 1})(p_{i + 1} - p_{i}) < 0。

对于全部的测试数据,保证 1≤T≤1201 \leq T \leq 120,3≤n≤N≤1063 \leq n \leq N \leq 10^6,输入的 pip_i 是一个排列。