#P9766. Queenfish

    ID: 6389 传统题 4000ms 2048MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS离线查询耐心排序求 LISSegment Tree Beats维护最大值与次大值懒标记线段树

Queenfish

题目描述

给定数组 x1,x2,…,xnx_1,x_2,\ldots,x_n 和常数 kk。需要支持两种操作。

  • 1 i y:将 xix_i 修改为 yy。
  • 2 l:在满足 l≤y1<y2<⋯<yk≤nl\le y_1<y_2<\cdots<y_k\le n 且 xy1<xy2<⋯<xykx_{y_1}<x_{y_2}<\cdots<x_{y_k} 的下标序列中,求最小的结束下标 yky_k。若不存在这样的序列,答案为 −1-1。

输入格式

第一行三个整数 n,m,kn,m,k,分别表示数组长度、操作次数和递增子序列的长度。

第二行 nn 个整数 x1,x2,…,xnx_1,x_2,\ldots,x_n。

接下来 mm 行,每行是 1 i y 或 2 l。其中 1≤i,l≤n1\le i,l\le n。

输出格式

每遇到一个 2 l 操作,输出一行一个整数作为答案。保证至少有一次此类操作。

样例

11 10 4
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
2 6
1 9 6
1 10 7
2 5
4
5
6
-1
-1
11

数据范围

1≤n,m≤5×1051\le n,m\le5\times10^5,3≤k≤43\le k\le4。初始值与每次赋入的值均为 [1,109][1,10^9] 内的整数。

原题列出四个各 25 分的子任务,条件依次为 k=4k=4 且所有 2 l 的 l=1l=1、k=4k=4 且 n,m≤105n,m\le10^5、k=3k=3、k=4k=4。

原题正文图 · 原题子任务图