#P8415. [THUPC2022 决赛] pmrmscxip

[THUPC2022 决赛] pmrmscxip

题目描述

给序列 a1,,ana_1,\dots,a_n 和排列 b1,,bnb_1,\dots,b_n,共有 mm 次操作:

修改操作:给定 x,yx,y,将 axa_x 改为 yy

查询操作:给定 l,r,xl,r,x,查区间 [l,r][l,r] 内最长的子区间 [l,r][l',r'](即满足 llrrl\le l'\le r'\le r),使得对 li<rl'\le i<r'ai+1=baia_{i+1}=b_{a_i},且存在 lirl'\le i\le r' 使得 ai=xa_i=x。需要输出满足条件的 rl+1r'-l'+1 的最大值,若不存在则输出 00

输入格式

第一行两个整数 n,mn,m

第二行 nn 个整数依次表示 a1,,ana_1,\dots,a_n

第三行 nn 个整数依次表示 b1,,bnb_1,\dots,b_n

接下来 mm 行,每行 1,x,y1,x,y2,l,r,x2,l,r,x 表示进行一次修改操作或查询操作。

输入的所有数值为整数。

输出格式

对每个查询操作,输出一行,表示相应的答案。

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

1
1
0
1
1
3
2
1
0

提示

1n,m1061\le n,m\le 10^6

1ain1\le a_i\le n

1bin1\le b_i\le nbib_i 互不相同;

对修改操作,满足 1x,yn1\le x,y\le n

对查询操作,满足 1lrn1\le l\le r\le n1xn1\le x\le n