F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5294. -- [Bjoi2018]二进制

5294: [Bjoi2018]二进制

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 174  Solved: 108
[Submit][Status][Discuss]

Description

pupil 发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是333 的倍数。他想研究对于二进
制,是否也有类似的性质。于是他生成了一个长为n 的二进制串,希望你对于这个二进制串的一个子区间,能求出
其有多少位置不同的连续子串,满足在重新排列后(可包含前导0 )是一个3 的倍数。两个位置不同的子区间指开
始位置不同或结束位置不同。由于他想尝试尽量多的情况,他有时会修改串中的一个位置,并且会进行多次询问。

Input

输入第一行包含一个正整数n ,表示二进制数的长度。
之后一行n 个空格隔开的整数,保证均是0 或1 ,表示该二进制串。
之后一行一个整数m ,表示询问和修改的总次数。
之后m 行每行为1 i,表示pupil 修改了串的第i个位置(0 变成1 或1 变成0 ),或2 l r
表示pupil 询问的子区间是[l,r] 。
串的下标从1 开始。
1≤n,m≤100000

Output

对于每次询问,输出一行一个整数表示对应该询问的结果。

Sample Input

4
1 0 1 0
3
2 1 3
1 3
2 3 4

Sample Output

2
3
说明
样例解释
对于第一个询问,区间[2,2] 只有数字0 ,是3 的倍数,区间[1,3]
可以重排成011(2)=3(10),是3 的倍数,其他区间均不能重排成3 的倍数。
对于第二个询问,全部三个区间均能重排成3 的倍数(注意00 也是合法的)。

HINT

Source

鸣谢佚名上传

[Submit][Status][Discuss]

HOME Back