[CERC2019] The Bugs

Luogu

IDLGP9617

Time500ms

Memory128MB

Difficulty—

2019O2优化ICPCCERC

一艘涂有明亮塑料柠檬色的潜艇正在调查海洋深度，并测量水中塑料 yocto 颗粒的浓度。每个测量值（由于巧妙地选择了单位）都是一个正整数。测量系统是最新的，很少测试，容易出错。项目管理层怀疑它充满了漏洞。他们发现自己陷入了困境。Mother Mary 也怀疑里面满是漏洞。大家都喊：救命！为了发现和修复这些漏洞，他们聚集在一起，决定采用浓度的测量序列，并分析测量序列中出现的所有三元组。 - 三元组是由三个整数组成的序列。 - 每个三元组都与其特征组相关。 - 三元组 $(x, y, z)$ 的特征组是三元组 $(\text{sgn}(y−x) ,\text{sgn}(z−y), \text{sgn}(z−x))$。对于 $x$ 的负值、零值或正值，$\text{sgn}(x)$ 函数的值分别为 $−1$、$0$ 或 $1$，即 $\text{sgn}(x)=\begin{cases}0&x=0\\\dfrac{x}{|x|}&x\ne 0\end{cases}$。 - 三元组 $(x_1, y_1, z_1)$ 小于三元组 $(x_2, y_2, z_2)$，当且仅当三元组 $(x_1-x_2, y_1-y_2, z_1-z_2)$ 中的第一个非零值为负。 - 三元组 $T$ 的标记组是一个最小的三元组，它的值都为正，并且其特征组等于 $T$ 的特征组。一个被测三元组是作为测量序列的子序列的三元组。也就是说，这个三元组的元素以它们在三元组中出现的相同顺序出现在测量序列中，但在序列中它们不一定相互跟随。在对它们进行分析之前，被测三元组根据它们的标记组进行分组。管理层希望提前知道所有测量的三元组的标记组的集合。 ## Input 第一行包含一个整数 $N\ (3\le N\le 2\times 10^5)$，代表测量序列的长度。第二行包含 $N$ 个整数 $x_1, x_2, x_N\ (1\le x_i\le 10^9)$，代表测量序列。 ## Output 按递增顺序输出所有被测三元组的所有不同标记组，这些标记组可以从给定的测量序列中获得，每行一个。输出标记组时，其连续元素之间不应有空格。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[The Bugs](https://contest.felk.cvut.cz/19cerc/solved/thebugs.pdf)」**

Samples

Input #1

5
1 2 3 4 5

Output #1

Input #2

6
5 4 9 1 7 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CERC2019] The Bugs",
    "description": {
      "content": "一艘涂有明亮塑料柠檬色的潜艇正在调查海洋深度，并测量水中塑料 yocto 颗粒的浓度。每个测量值（由于巧妙地选择了单位）都是一个正整数。 测量系统是最新的，很少测试，容易出错。项目管理层怀疑它充满了漏洞。他们发现自己陷入了困境。Mother Mary 也怀疑里面满是漏洞。大家都喊：救命！ 为了发现和修复这些漏洞，他们聚集在一起，决定采用浓度的测量序列，并分析测量序列中出现的所有三元组。 - ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9617"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一艘涂有明亮塑料柠檬色的潜艇正在调查海洋深度，并测量水中塑料 yocto 颗粒的浓度。每个测量值（由于巧妙地选择了单位）都是一个正整数。\n\n测量系统是最新的，很少测试，容易出错。项目管理层怀疑它充满了漏洞。他们发现自己陷入了困境。Mother Mary 也怀疑里面满是漏洞。大家都喊：救命！\n\n为了发现和修复这些漏洞，他们聚集在一起，决定采用浓度的测量序列，并分析测量序列中出现的所有三元组。\n\n- ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments