{"problem":{"name":"[Ynoi2000] rspcn","description":{"content":"给定整数序列 $a_1,\\dots,a_n$ ，共 $m$ 次操作； 每次操作给出 $l,r,x$ ，首先进行修改，然后查询 $a_1,\\dots,a_x$ 中有多少种不同的值。 若 $l\\le r$ ，则进行的修改是将 $a_l,\\dots,a_r$ 从小到大排序；否则进行的修改是将 $a_r,\\dots,a_l$ 从大到小排序。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":8000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9995"},"statements":[{"statement_type":"Markdown","content":"给定整数序列 $a_1,\\dots,a_n$ ，共 $m$ 次操作；\n\n每次操作给出 $l,r,x$ ，首先进行修改，然后查询 $a_1,\\dots,a_x$ 中有多少种不同的值。\n\n若 $l\\le r$ ，则进行的修改是将 $a_l,\\dots,a_r$ 从小到大排序；否则进行的修改是将 $a_r,\\dots,a_l$ 从大到小排序。\n\n## Input\n\n第一行两个整数 $n,m$ ；\n\n第二行 $n$ 个整数 $a_1,\\dots,a_n$ ；\n\n接下来 $m$ 行，每行三个整数 $l\\oplus c,r\\oplus c,x\\oplus c$ ，依次表示每次操作，其中 $\\oplus$ 是按位异或，$c$ 是上次操作的查询的答案（特别地，对于第一次操作，$c=0$）。\n\n## Output\n\n共 $m$ 行，每行一个整数，依次表示每次操作的查询的答案。\n\n[samples]\n\n## Note\n\nIdea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $20\\%$ 的数据，满足 $n,m\\le 10^3$。\n\n对于另外 $20\\%$ 的数据，满足 $a_i\\le 10$。\n\n对于另外 $20\\%$ 的数据，满足 $a_i\\le 100$。\n\n对于另外 $20\\%$ 的数据，满足 $n,m\\le 10^5$。\n\n对于 $100\\%$ 的数据，满足 $1\\le a_i\\le n$，$1\\le l,r,x\\le n$，$1\\le n,m\\le 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9995","tags":["2000","O2优化","Ynoi"],"sample_group":[["9 7\n2 2 8 8 2 8 2 1 3\n2 2 2\n3 7 6\n6 7 1\n9 6 7\n10 11 10\n7 0 5\n5 1 7","1\n2\n1\n2\n3\n2\n2"]],"created_at":"2026-03-03 11:09:25"}}