#P13486. [ABC324G] Generate Arrays

    ID: 12670 传统题 6000ms 1024MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300提高可持久化线段树路径复制前缀版本作差线段树上二分

[ABC324G] Generate Arrays

AT_abc324_g [ABC324G] Generate Arrays

6s,1g

题目描述

高桥君有一个长度为 NN 的数列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。AA 是 1,2,…,N1,2,\ldots,N 的一个排列。

高桥君要进行 QQ 次操作,生成 1+Q1+Q 个数列。将 00 号数列定义为 AA,高桥君从此开始一系列操作。第 ii 次操作(1≤i≤Q1\leq i\leq Q)用整数三元组 (ti,si,xi)(t_i,s_i,x_i) 表示,对应如下操作(也请参考输入输出样例的说明):

  • 当 ti=1t_i=1 时,高桥君从 sis_i 号(0≤si<i0\leq s_i<i)数列中,去除第 xix_i 个元素之后的所有元素,并将这些被去除的元素按原顺序组成新的 ii 号数列。
  • 当 ti=2t_i=2 时,高桥君从 sis_i 号(0≤si<i0\leq s_i<i)数列中,去除所有值大于 xix_i 的元素,并将这些被去除的元素按原顺序组成新的 ii 号数列。

注意,对于长度为 LL 的数列 XX,XX 的所有元素都被认为是“第 00 个元素之后的元素”。对于任意 l≥Ll\geq L,XX 的所有元素都不是“第 ll 个元素之后的元素”。

请你求出对于 i=1,2,…,Qi=1,2,\ldots,Q,每次操作结束后,第 ii 号数列的长度。

输入格式

输入按以下格式从标准输入给出。

NN A1A_1 A2A_2 …\ldots ANA_N QQ t1t_1 s1s_1 x1x_1 t2t_2 s2s_2 x2x_2 ⋮\vdots tQt_Q sQs_Q xQx_Q

输出格式

请输出 QQ 行。第 ii 行(1≤i≤Q1\leq i\leq Q)输出第 ii 次操作结束后第 ii 号数列的长度。

输入输出样例 #1

输入 #1

10
1 8 7 4 5 6 3 2 9 10
5
2 0 4
1 1 2
2 0 2
2 2 5
1 0 1

输出 #1

6
4
2
3
1

输入输出样例 #2

输入 #2

8
6 7 8 4 5 1 3 2
5
2 0 0
1 1 0
2 2 0
1 3 8
2 2 3

输出 #2

8
8
8
0
0

输入输出样例 #3

输入 #3

30
20 6 13 11 29 30 9 10 16 5 8 25 1 19 12 18 7 2 4 27 3 22 23 24 28 21 14 26 15 17
10
1 0 22
1 0 21
2 0 15
1 0 9
1 3 6
2 3 18
1 6 2
1 0 1
2 5 20
2 7 26

输出 #3

8
1
8
4
2
5
3
8
1
1

说明/提示

约束条件

  • 1≤N≤2×1051\leq N\leq 2\times 10^5
  • 1≤Ai≤N (1≤i≤N)1\leq A_i\leq N\ (1\leq i\leq N)
  • Ai≠Aj (1≤i<j≤N)A_i\neq A_j\ (1\leq i<j\leq N)
  • 1≤Q≤2×1051\leq Q\leq 2\times 10^5
  • ti=1,2 (1≤i≤Q)t_i=1,2\ (1\leq i\leq Q)
  • 0≤si<i (1≤i≤Q)0\leq s_i<i\ (1\leq i\leq Q)
  • 0≤xi≤N (1≤i≤Q)0\leq x_i\leq N\ (1\leq i\leq Q)
  • 输入均为整数

样例解释 1

一开始,高桥君有长度为 1010 的数列 A=(1,8,7,4,5,6,3,2,9,10)A=(1,8,7,4,5,6,3,2,9,10)。高桥君以 00 号数列 A=(1,8,7,4,5,6,3,2,9,10)A=(1,8,7,4,5,6,3,2,9,10) 开始一系列操作。第 11 次操作,从 00 号数列中去除大于 44 的元素 8,7,5,6,9,108,7,5,6,9,10,并将这些元素组成新的 11 号数列。操作后,0,10,1 号数列分别为 (1,4,3,2),(8,7,5,6,9,10)(1,4,3,2),(8,7,5,6,9,10)。第 22 次操作,从 11 号数列中去除第 22 个元素之后的元素 5,6,9,105,6,9,10,并将这些元素组成新的 22 号数列。操作后,0,1,20,1,2 号数列分别为 (1,4,3,2),(8,7),(5,6,9,10)(1,4,3,2),(8,7),(5,6,9,10)。第 33 次及以后的操作,每次操作结束后 0,1,2,…,i0,1,2,\ldots,i 号数列分别如下:

  • (1,2),(8,7),(5,6,9,10),(4,3)(1,2),(8,7),(5,6,9,10),(4,3)
  • (1,2),(8,7),(5),(4,3),(6,9,10)(1,2),(8,7),(5),(4,3),(6,9,10)
  • (1),(8,7),(5),(4,3),(6,9,10),(2)(1),(8,7),(5),(4,3),(6,9,10),(2)

对于 i=1,2,…,5i=1,2,\ldots,5,每次操作结束后第 ii 号数列的长度分别为 6,4,2,3,16,4,2,3,1,请按顺序输出。

样例解释 2

操作结果可能会出现空数列。