QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB

# 7992. 【模板】线段树

统计

题目描述

有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$,保证 $a_i$ 为奇数

有两种操作:

  1. 给定 $l,r,x$,将 $a_l,a_{l+1},\cdots,a_r$ 加上偶数 $x$;
  2. 给定 $l,r$,求 $a_l,a_{l+1},\cdots,a_r$ 的乘积,答案对 $2^{20}$ 取模;

输入格式

从标准输入读入数据。

第一行两个正整数 $n,q$ 表示序列的长度和询问的个数. 保证 $1 \le n,q \le 2\times 10^5$。

第二行 $n$ 个奇数 $a_1,a_2,\cdots,a_n$. 保证 $1 \le a_i < 2^{20}$。

接下来 $q$ 行,每一行表示一个操作,格式为以下两种之一:

  • $1 ~ l ~ r ~ x$:表示进行第一种操作. 保证 $1 \le l \le r \le n$,$0 \le x < 2 ^ {20}$。
  • $2 ~ l ~ r$:表示进行第二种操作. 保证 $1 \le l \le r \le n$。

输出格式

输出到标准输出。

对于每一次 $2$ 操作,输出一行一个整数表示答案。

样例

输入

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323 
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

输出

1045541
1012343
558151
580413
810659
527353