题目描述
军军有一个⻓度为n 的序列a 。
军军在这个序列上乱玩。他有两种玩法:
1. 选定一段子区间,询问该区间所代表的序列有多少个不同的子序列。
2. 区间修改,选定一个区间,一个区间的数全部覆盖成指定的数。
这种毒瘤题当然就交给了会修电脑的OIer/ACMer 你了。
为了方便,分别输出答案对于39989 取模后的结果。
输入
第一行两个正整数n;m 分别表示序列⻓度和操作次数。
第二行n 个正整数,第i 个数是ai 。
接下来有m 行,每行第一个整数为opt ,
如果opt = 0 ,则接下来3 个整数x, y, v 表示将区间[x, y] 的所有数的值改成v ;
如果opt = 1 ,则接下来两个整数x, y ,表示询问区间[x, y] 。
1 <= n,m <= 50000; 1 <= ai,v <= 4 。
输出
对于每一次询问,分别输出答案对于39989 取模后的结果。
样例输入
10 10
3 3 1 1 4 2 2 4 1 4
0 1 8 4
1 5 7
1 6 8
1 2 9
1 1 5
0 6 9 4
1 2 4
1 1 1
0 6 10 1
0 3 10 2
样例输出
4
4
16
6
4
2
来源/分类
2018年学军中学校赛