UOJ Logo Universal Online Judge

UOJ

#671. 【UNR #5】诡异操作

附件下载 统计

UOI 虽然非常高级,在赛时就可以得到成绩。但是在比赛结束的一刹那,一条外星亖手蚯蚓钻进了存储着比赛成绩的机器里,随即机器开始冒烟。

外星亖手蚯蚓立刻被众人控制住了,勒令将比赛成绩从该机器的数据盘里恢复出来。可是亖手蚯蚓脑回路比较奇怪,所以恢复数据的方式也非常的怪。

在一开始,数据盘里面存储着一个整数序列 $a$。然后每一步,亖手蚯蚓会先给定一个区间 $[l, r] (1 \leq l \leq r \leq n)$。然后进行以下三种操作之一:

  • $1\ l\ r\ v$: 给定 $v$, 对于 $l \leq i \leq r$,将 $a_i$ 变为 $\lfloor \frac{a_i}{v} \rfloor$。这里我们保证 $v \ge 1$。

  • $2\ l\ r\ v$: 给定 $v$, 对于 $l \leq i \leq r$,将 $a_i$ 变为 $a_i \& v$,其中 $\&$ 是按位与运算。

  • $3\ l\ r$: 向你询问 $a_i$($l \leq i \leq r$)的总和。

虽然你不太理解亖手蚯蚓这通诡异的操作,但你还是乖乖地回答着亖手蚯蚓的一个个询问。不过有没有可能做得快一点呢?

输入格式

第一行两个正整数 $n, q$,表示序列 $a$ 的长度和询问个数。

下面一行 $n$ 个整数 $a_i$,以 $16$ 进制读入

下面 $q$ 行,每行第一个正整数 $op_i$ 表示操作编号。

对于 $op_i = 1$ 或 $op_i = 2$,后面紧跟三个整数 $l_i, r_i, v_i$,表示执行上述对应操作, 其中 $v_i$ 以 $16$ 进制读入

对于 $op_i = 3$,后面紧跟两个整数 $l_i, r_i$,表示询问这个区间的元素的和对 $2^{128}$ 取模的值,以 $16$ 进制输出

在本题中所有的十六进制数 仅包含字符 0 $\sim$ 9,a $\sim$ f,分别代表着 $0 \sim 9,10 \sim 15$,同时 不存在无效前导零 。本题的所有 $16$ 进制输入保证满足如上格式,选手的输出也需要满足如上格式。

提示: UOJ 中可以使用 $128$ 位无符号整型数字 __uint128_t,但需要手动实现 IO,我们提供了 IO 模板在题面结尾。

输出格式

若干行,对于每个询问,输出其答案。

样例一

input

5 5
1 9 1 9 1
3 2 3
2 1 3 5
3 1 5
1 1 5 3
3 1 5

output

a
d
3

样例二

见附加文件中 ex_machine2.inex_machine2.out

样例三

见附加文件中 ex_machine3.inex_machine3.out,其中所有数不超过 $2^{40}$。

限制与约定

对于 $100\%$ 的数据,$1 \leq l_i \leq r_i \leq n \leq 300000, 1 \leq q \leq 200000, 0 \leq v_i, a_i \lt 2^{128}$,其中操作一的 $v_i \geq 1$。

子任务编号 $n\le$ $q\le$ 特殊性质 分值
$1$ $3000$ $3000$ $15$
$2$ $3\times 10^5$ $2\times 10^5$ $op_i \neq 2$ $20$
$3$ $l_i = 1, r_i = n$ $20$
$4$ $op_i \neq 1$ $20$
$5$ $25$

时间限制:$\texttt{3s}$

空间限制:$\texttt{1GB}$

提示

提示:请注意你的算法的时间复杂度。

提示: UOJ 中可以使用 $128$ 位无符号整型数字 __uint128_t,但需要手动实现 IO,我们在下方提供了模板。

typedef __uint128_t u128;
inline u128 read() {
    static char buf[100];
    scanf("%s", buf);
    // std::cin >> buf;
    u128 res = 0;
    for(int i = 0;buf[i];++i) {
        res = res << 4 | (buf[i] <= '9' ? buf[i] - '0' : buf[i] - 'a' + 10);
    }
    return res;
}
inline void output(u128 res) {
    if(res >= 16)
        output(res / 16);
    putchar(res % 16 >= 10 ? 'a' + res % 16 - 10 : '0' + res % 16);
    //std::cout.put(res % 16 >= 10 ? 'a' + res % 16 - 10 : '0' + res % 16);
}