1468: sequence

题目描述


军军有一个⻓度为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年学军中学校赛

请先 登录 后评论
  • 0 关注
  • 0 收藏,462 浏览
  • 轩爸 提出于 2019-08-02 22:09

相似问题