[Ynoi2000] rspcn

Luogu
IDLGP9995
Time8000ms
Memory512MB
DifficultyP6
2000O2优化Ynoi
给定整数序列 $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$ 从大到小排序。 ## Input 第一行两个整数 $n,m$ ; 第二行 $n$ 个整数 $a_1,\dots,a_n$ ; 接下来 $m$ 行,每行三个整数 $l\oplus c,r\oplus c,x\oplus c$ ,依次表示每次操作,其中 $\oplus$ 是按位异或,$c$ 是上次操作的查询的答案(特别地,对于第一次操作,$c=0$)。 ## Output 共 $m$ 行,每行一个整数,依次表示每次操作的查询的答案。 [samples] ## Note Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078 对于 $20\%$ 的数据,满足 $n,m\le 10^3$。 对于另外 $20\%$ 的数据,满足 $a_i\le 10$。 对于另外 $20\%$ 的数据,满足 $a_i\le 100$。 对于另外 $20\%$ 的数据,满足 $n,m\le 10^5$。 对于 $100\%$ 的数据,满足 $1\le a_i\le n$,$1\le l,r,x\le n$,$1\le n,m\le 10^6$。
Samples
Input #1
9 7
2 2 8 8 2 8 2 1 3
2 2 2
3 7 6
6 7 1
9 6 7
10 11 10
7 0 5
5 1 7
Output #1
1
2
1
2
3
2
2
API Response (JSON)
{
  "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第二...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments