TLEoj Contest #05 - Truy vấn AOX (bản khó)

Điểm: 2300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

khanhphucscratch, huyhau6a2

Dạng bài

Chắc hẳn các bạn còn nhớ bài TLE-oj Cup Round 6 - Truy vấn AOX của huyhau6a2. Đây là bản khó của bài tập này. Bản khó và bản dễ chỉ khác nhau về phần dữ liệu

Bạn được cho 1 xâu $a$ gồm $n$ ký tự chỉ gồm các ký tự như &, |, ^ (tương đương với phép toán AND, OR, XOR). Bạn phải thực hiện $q$ truy vấn:

$1$ $k$ $x$ : Cập nhật ký tự thứ $k$ trong xâu $a$ thành $x$ ( $1\le k\le n$ , $x$ thuộc 1 trong 3 loại ký tự như trên)
$2$ $l$ $r$ $k$ $u$ $v$ : Tính độ đẹp của xâu trong đoạn $[l,r]$ với các giá trị $k,u,v$ ( $1\le l\le r\le n,1\le k\le 60,0\le u\le v<2^k$ )

huyhau6a2 định nghĩa độ đẹp của một xâu ký tự $a$ độ dài $x$ với các giá trị $k,u,v$ như sau: Là số lượng dãy $b$ thỏa mãn ( $0\le b_i<2^k$ ):

$u\le b_1\ a_1\ b_2\ a_2\ b_3\ a_3\ b_4\ \dots\ a_x\ b_{x+1}\le v$

Chú ý: Thứ tự thực hiện tính toán theo các ký tự của xâu $a$ được thực hiện từ trái sang phải

VD: Xâu |^ với $k=1,u=1,v=1$ thì có các khả năng như sau:

0|0^0=0
0|0^1=1
0|1^0=1
0|1^1=0
1|0^0=1
1|0^1=0
1|1^0=1
1|1^1=0

Theo như kết quả ở trên, có 4 kết quả thỏa mãn. Vậy độ đẹp của xâu |^ với $k=1,u=1,v=1$ là $4$

Nhiệm vụ của bạn là phải tính toán các kết quả của truy vấn 2. Vì kết quả rất lớn nên hãy xuất kết quả $mod\ 10^9+7$

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên gồm 2 số $n$ và $q$ ( $1\leq n,q\leq 2\cdot 10^5$ )
Dòng thứ hai gồm duy nhất một xâu $a$
Sau đó là $q$ dòng, mỗi dòng nhập truy vấn như trên

Output: (màn hình)

Với mỗi truy vấn loại 2, xuất ra kết quả cần tìm

Subtasks

Bài toán sẽ chia làm 3 nhóm subtask:

Nhóm subtask 1 $(10\%)$ : $n,q\le 20$
Nhóm subtask 2 $(30\%)$ : $n,q\le 5000$
Nhóm subtask 3 $(60\%)$ : $n,q\le 2\cdot 10^5$

Với mỗi nhóm subtask sẽ có ràng buộc về các loại truy vấn như sau:

Ràng buộc 1 $(10\%)$ : $u=0,v=2^k-1$ với mọi truy vấn loại 2.
Ràng buộc 2 $(20\%)$ : $k=1$ với mọi truy vấn loại 2.
Ràng buộc 3 $(20\%)$ : $k\le 20$ với mọi truy vấn loại 2.
Ràng buộc 4 $(50\%)$ : Không có ràng buộc gì thêm

Sample

Input (bàn phím)

3 4
&|^
2 2 3 1 1 1
1 3 |
2 2 3 1 0 1
2 1 3 2 2 2

Output (màn hình)

4
8
39

Note

Trong truy vấn 1 đã giải thích ở trên nên sẽ không giải thích lại.
Trong truy vấn 2 dễ dàng nhận thấy với mọi dãy $b$ kết quả có thể ra trong khoảng $[0,1]$ , mà có $8$ dãy $b$ có thể tạo nên xuất ra $8$

Bình luận

Không có bình luận nào.