{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"You need to write a data structure (refer to the title of the problem) to maintain a sorted sequence, which needs to provide the following operations:\n\n1. Query the rank of $k$ within the interval\n\n2. Query the value that ranks $k$ within the interval\n\n3. Modify the value at a certain position\n\n4. Query the predecessor of $k$ within the interval (the predecessor is defined as the largest number that is strictly less than $x$, **if it does not exist, output `-2147483647`**)\n\n5. Query the successor of $k$ within the interval (the successor is defined as the smallest number that is strictly greater than $x$, **if it does not exist, output `2147483647`**)"}},{"title":"Input","value":{"format":"MD","content":"The first line contains two numbers $n,m$, indicating a sorted sequence of length $n$ and $m$ operations.\n\nThe second line contains $n$ numbers, indicating the sorted sequence.\n\nThere are $m$ lines below, $opt$ indicates the operation number.\n\nIf $opt\u003d1$, it is operation $1$, followed by three numbers $l~r~k$, indicating to query the rank of $k$ within the interval $[l,r]$.\n\nIf $opt\u003d2$, it is operation $2$, followed by three numbers $l~r~k$, indicating to query the value that ranks $k$ within the interval $[l,r]$.\n\nIf $opt\u003d3$, it is operation $3$, followed by two numbers $pos~k$, indicating to modify the number at position $pos$ to $k$.\n\nIf $opt\u003d4$, it is operation $4$, followed by three numbers $l~r~k$, indicating to query the predecessor of $k$ within the interval $[l,r]$.\n\nIf $opt\u003d5$, it is operation $5$, followed by three numbers $l~r~k$, indicating to query the successor of $k$ within the interval $[l,r]$."}},{"title":"Output","value":{"format":"MD","content":"For operation $1,2,4,5$, output one line each, indicating the query results."}},{"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\u003e9 6\n4 2 2 1 9 4 0 1 1\n2 1 4 3\n3 4 10\n2 1 4 3\n1 2 5 9\n4 3 9 5\n5 2 8 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n3\n4\n9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"$1\\le n,m\\le5\\times 10^4$, the values in the sequence at any time $\\in[0,10^8]$.\n\nProblem source: bzoj3196 / Tyvj1730, special thanks.\n\nThis data is original from Luogu. **(Special reminder: This data does not guarantee that operations 4 and 5 will definitely exist, so please be sure to consider the case where they do not exist.)**"}}]}