QOJ.ac

QOJ

Time Limit: 15 s Memory Limit: 2048 MB
[0]

# 4316. pmrmscxip

统计

题目描述

给序列 a1,,an 和排列 b1,,bn,共有 m 次操作:

修改操作:给定 x,y,将 ax 改为 y

查询操作:给定 l,r,x,查区间 [l,r] 内最长的子区间 [l,r](即满足 llrr),使得对 li<rai+1=bai,且存在 lir 使得 ai=x。只需输出 rl+1 的最大值,若不存在则输出 0

输入格式

第一行两个整数 n,m

第二行 n 个整数依次表示 a1,,an

第三行 n 个整数依次表示 b1,,bn

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

1n,m106

1ain

1binbi 互不相同;

对修改操作,满足 1x,yn

对查询操作,满足 1lrn1xn

输入的所有数值为整数。

输出格式

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

样例数据

样例输入

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