HS读法书

【数据生成】

哈哈，想自测就把下面代码打下来吧！

【题目描述】

hs有一本法书，可以表示为一个长为n的数组a[1..n]。由于是法书，这个数组还可能会改变。好奇的J看到后，希望进行一些询问，每次询问给出l,r,x,y，求有多少个极大下标集合，其中的下标连续且在[l,r]内，且同一集合中的下标对应的数组中元素均相同且在[x,y]内。

【输入格式】

第一行输入n,m；

接下来一行n个数表示初始数列ai；

接下来m个操作，操作有如下两种：

1 k w：ak变成了w；

2 l r x y：表示询问。

【输出格式】

对于每个询问输出答案。

【样例输入】

5 5
3 3 3 5 5
2 2 3 4 5
2 2 3 3 4
1 3 1
2 1 5 3 5
2 2 3 1 4

【样例输出】

0
1
2
2

【提示】

对于30%的数据，n,m≤1000；

对于所有数据，1≤ai≤n，1≤n,m≤100000。

【来源】

luogu and hs