Problem1403--#6061. 「2017 山东一轮集训 Day1」Sim

1403: #6061. 「2017 山东一轮集训 Day1」Sim

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个含 n n n 个正整数的数组 A A A。现有关于它的 Q Q Q 个询问,询问有以下五种类型:

  • 1 l r,令 S S S 为由下标范围从 l l lr r r 的不同的元素构成的有序集合,你需要求出

    1i<j<k|S|SiSjSk(mod109+7)

  • 2 x y,将下标为 x x x 的元素赋值 y y y
  • 3 x,将下标为 x x x 的元素从数组中删除
  • 4 z y,在下标为 z z z 的元素之后插入元素 y y y(若 z z z 等于 0 0 0,则在数组最前端插入)
  • 5 l r,输出下标在 l l lr r r 范围内的不同元素个数

数组下标从 1 1 1 开始,数据保证数组总是非空。

Input

输入数据第一行包含两个整数 n n nq q q,分别表示 A A A 的长度,以及询问的数量。
第二行包括 n n n 个整数,表示给定的数组 A A A
接下来的 q q q 行,每行包含一个询问,格式见题面。

Output

对于每次类型 1 和类型 5 的询问,输出一行包含相应的答案。

Sample Input Copy

5 8
1 2 3 2 1
1 1 3
5 1 5
2 2 4
1 2 4
3 3
4 0 5
1 1 2
1 1 5

Sample Output Copy

6
3
24
0
78

HINT

对于所有数据,1≤n,q≤105;1≤Ai,y≤109+6;1≤x≤∣A∣;0≤z≤∣A∣;1≤l≤r≤∣A∣ 1 \leq n, q \leq 10 ^ 5; 1 \leq A_i, y \leq 10 ^ 9 + 6; 1 \leq x \leq |A|; 0 \leq z \leq |A|; 1 \leq l \leq r \leq |A| 1n,q105;1Ai,y109+6;1xA;0zA;1lrA

另有如下互不重合的特殊数据:

  • 10% 10\% 10%1≤n,q≤100 1 \leq n, q \leq 100 1n,q100
  • 20% 20\% 20%,只含类型 2、5
  • 20% 20\% 20%,只含类型 1、2、5
  • 20% 20\% 20%,不含类型 1
  • 10% 10\% 10%,不含类型 5
  • 10% 10\% 10%1≤n,q≤50000 1 \leq n, q \leq 50000 1n,q50000

Source/Category