{"problem":{"name":"「LAOI-4」石头","description":{"content":"有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。 现在我们称满足以下要求的数对 $(i,j)$ 是好的数对： - $1\\leq i\\leq j\\leq n$。 - 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10371"},"statements":[{"statement_type":"Markdown","content":"有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。\n\n现在我们称满足以下要求的数对 $(i,j)$ 是好的数对：\n\n- $1\\leq i\\leq j\\leq n$。\n- 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a_i$ 也会在第 $k$ 步被染白。\n\n求好的数对的数量。\n\n## Input\n\n由于输入数据过大，现给出数据辅助生成器。\n\n```cpp\nint a[/*数组大小*/];\nnamespace GenHelper\n{\n    unsigned z1, z2, z3, z4, b;\n    unsigned rand_()\n    {\n        b = ((z1 << 6) ^ z1) >> 13;\n        z1 = ((z1 & 4294967294U) << 18) ^ b;\n        b = ((z2 << 2) ^ z2) >> 27;\n        z2 = ((z2 & 4294967288U) << 2) ^ b;\n        b = ((z3 << 13) ^ z3) >> 21;\n        z3 = ((z3 & 4294967280U) << 7) ^ b;\n        b = ((z4 << 3) ^ z4) >> 12;\n        z4 = ((z4 & 4294967168U) << 13) ^ b;\n        return (z1 ^ z2 ^ z3 ^ z4);\n    }\n}\nvoid srand_(unsigned x, int n)\n{\n    using namespace GenHelper;\n    z1 = x;\n    z2 = (~x) ^ 0x233333333U;\n    z3 = x ^ 0x1234598766U;\n    z4 = (~x) + 51;\n    for (int i = 1; i <= n; ++i)\n        a[i] = i;\n    if (!x)\n        return;\n    for (int i = 1; i <= n; ++i)\n    {\n        int j = rand_() % i + 1, k;\n        k = a[i], a[i] = a[j], a[j] = k;\n    }\n}\n```\n\n输入两个整数 $n$ 和 $s$，分别表示排列长度和随机数种子。\n\n你需要恰好调用一次 `srand_(s,n)`，在此之后 $a_i$ 已经储存在 `a[i]` 中，注意下标从 $1$ 开始，不要忘记规定数组大小。\n\n## Output\n\n共一行一个正整数，表示好的数对的数量。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n对于样例组 #1，$a=\\{4,3,1,5,2\\}$，好的数对分别是：$(1,1),(1,3),(1,5),(2,2),(2,3),(2,4),(3,3),(4,4),(5,5)$。\n\n### 数据范围\n\n**「本题采用捆绑测试」**\n\n|子任务编号|$n$|特殊性质|分值|\n|:-:|:-:|:-:|:-:|\n|$1$|$\\le10^3$|无|$15$|\n|$2$|$\\le10^5$|无|$30$|\n|$3$|$\\le10^7$|$\\text{A}$|$5$|\n|$4$|$\\le10^7$|无|$50$|\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\le 10^7$，$0\\leq s\\leq 114514$，$a$ 为 $n$ 的排列。  \n\n特殊性质 $\\text{A}$：$a_i$ 单调递增，此时 $s=0$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10371","tags":["洛谷原创","O2优化","链表","单调栈","洛谷比赛"],"sample_group":[["5 114514","9"],["10 113037","23"],["20 73555","49"]],"created_at":"2026-03-03 11:09:25"}}