A6085. 「BJOI2018」二进制
编程题
省选/NOI-
知识点
题目描述
pupil 发现对于一个十进制数，无论怎么将其的数字重新排列，均不影响其是不是 $3$ 的倍数。他想研究对于二进制，是否也有类似的性质。
于是他生成了一个长为 $n$ 的二进制串，希望你对于这个二进制串的一个子区间，能求出其有多少位置不同的连续子串，满足在重新排列后（可包含前导 $0$）是一个 $3$ 的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。
由于他想尝试尽量多的情况，他有时会修改串中的一个位置，并且会进行多次询问。
于是他生成了一个长为 $n$ 的二进制串，希望你对于这个二进制串的一个子区间，能求出其有多少位置不同的连续子串，满足在重新排列后（可包含前导 $0$）是一个 $3$ 的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。
由于他想尝试尽量多的情况，他有时会修改串中的一个位置，并且会进行多次询问。
输入格式
输入第一行包含一个正整数 $n$，表示二进制数的长度。
之后一行 $n$ 个空格隔开的整数，保证均是 $0$ 或 $1$，表示该二进制串。
之后一行一个整数 $m$，表示询问和修改的总次数。
之后 $m$ 行每行为 $1\ i$，表示 pupil 修改了串的第 $i$ 个位置（$0$ 变成 $1$ 或 $1$ 变成 $0$ ），或 $2\ l\ r$，表示 pupil 询问的子区间是 $[l,r]$。
串的下标从 $1$ 开始。
之后一行 $n$ 个空格隔开的整数，保证均是 $0$ 或 $1$，表示该二进制串。
之后一行一个整数 $m$，表示询问和修改的总次数。
之后 $m$ 行每行为 $1\ i$，表示 pupil 修改了串的第 $i$ 个位置（$0$ 变成 $1$ 或 $1$ 变成 $0$ ），或 $2\ l\ r$，表示 pupil 询问的子区间是 $[l,r]$。
串的下标从 $1$ 开始。
输出格式
对于每次询问，输出一行一个整数表示对应该询问的结果。
输入输出样例
输入 #1
4 1 0 1 0 3 2 1 3 1 3 2 3 4
输出 #1
2 3
说明/提示
对于 $20\%$ 的数据，$1 \leq n,m \leq 100$；
对于 $50\%$ 的数据，$1 \leq n,m \leq 5000$；
对于 $100\%$ 的数据，$1 \leq n,m \leq 100000$，$l \leq r$。
对于 $50\%$ 的数据，$1 \leq n,m \leq 5000$；
对于 $100\%$ 的数据，$1 \leq n,m \leq 100000$，$l \leq r$。