#PQJ397x2978. QOJ 397_2978
QOJ 397_2978
北京信息学集训队结业考试 第一试二进制(binary) 二进制(binary) 【题目描述】 pupil 发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是 3 的倍数。他想研究对于二进制,是否也有类似的性质。于是他生成了一个长为n 的二 进制串,希望你对于这个二进制串的一个子区间,能求出其有多少位置不同的连续子 串,满足在重新排列后(可包含前导0)是一个3 的倍数。两个位置不同的子区间指开 始位置不同或结束位置不同。由于他想尝试尽量多的情况,他有时会修改串中的一个位 置,并且会进行多次询问。 【输入格式】 从文件binary.in 中读入数据。 输入第一行包含一个正整数n,表示二进制数的长度。 之后一行n 个空格隔开的整数,保证均是0 或1,表示该二进制串。 之后一行一个整数m ,表示询问和修改的总次数。 之后m 行每行为1 i,表示pupil 修改了串的第i 个位置(0 变成1 或1 变成0 ), 或2 l r,表示pupil 询问的子区间是[l,r]。 串的下标从1 开始。 【输出格式】 输出到文件binary.out 中。 对于每次询问,输出一行一个整数表示对应该询问的结果。 【样例1 输入】 4 1 0 1 0 3 2 1 3 1 3 2 3 4 【样例1 输出】 2 3 第2 页 共7 页
北京信息学集训队结业考试 第一试二进制(binary) 【样例1 解释】 对于第一个询问,区间[2,2] 只有数字0,是3 的倍数,区间[1,3] 可以重排成 011(2) = 3(10),是3 的倍数,其他区间均不能重排成3 的倍数。 对于第二个询问,全部三个区间均能重排成3 的倍数(注意00 也是合法的)。 【子任务】 对于20% 的数据,1 ≤n, m ≤100。 对于50% 的数据,1 ≤n, m ≤5000。 对于100% 的数据,1 ≤n, m ≤100000,l ≤r。 第3 页 共7 页