Not Another Range Query Problem
题目描述
都什么年代了,你还在做传统的区间查询题?
小青鱼是区间查询题的头号爱好者,他想找到 3202 年最好的区间查询题。幸运的是,他发现了一道二进制字符串问题。他很喜欢二进制字符串,因为它们曾在 2202 年带来过 Best Problem。
对于长度为 n 的二进制字符串 s=s1s2⋯sn,定义 L(s) 为所有满足下列条件的位置 i(1≤i≤n)组成的集合:i=1,或者 si=si−1。
例如,L(0011100)={1,3,6},L(00101101)={1,3,4,5,7,8},L(000)={1}。特别地,若 s=ε 是空串,则 L(ε)=∅。
令 f(s) 为从 s 中同时删除所有下标属于 L(s) 的字符后得到的字符串。下表来自原 PDF,下划线表示本次被删除的字符:

表中的结果依次为:f(0011100)=0110,f(00101101)=01,f(000)=00,f(01)=ε,f(ε)=ε。
小青鱼发现的问题要求求出 fk(s) 的长度,其中
$$f^k(s)=\begin{cases}f^{k-1}(f(s)),&k\ge1,\\s,&k=0.\end{cases}$$
小青鱼希望将它变为区间查询问题。因此,他给你字符串 s=s1s2⋯sn 和 q 次查询。每次给出三个整数 l,r,k,你需要输出 fk(s[l⋯r]) 的长度,其中 s[l⋯r]=slsl+1⋯sr。
输入格式
第一行包含两个整数 n,q(1≤n,q≤5×105),分别表示字符串长度和查询次数。
第二行包含一个二进制字符串 s(∣s∣=n,si∈{0,1})。
接下来 q 行,每行描述一次查询,包含三个整数 l,r,k(1≤l≤r≤n,0≤k≤n)。
输出格式
对于每次查询,输出一行一个整数,表示 fk(s[l⋯r]) 的长度。
样例输入
9 7
100110001
2 5 1
3 6 1
4 8 2
2 7 1
1 9 1
1 9 0
1 9 8
样例输出
2
1
1
3
4
9
0
样例解释
- s[2⋯5]=0011,f(0011)=01,所以答案是 2。
- s[3⋯6]=0110,f(0110)=1,所以答案是 1。
- s[4⋯8]=11000,f2(11000)=f(100)=0,所以答案是 1。
- s[2⋯7]=001100,f(001100)=010,所以答案是 3。
- s[1⋯9]=100110001,f(100110001)=0100,所以答案是 4。
- s[1⋯9]=100110001,f0(100110001)=100110001,所以答案是 9。
- s[1⋯9]=100110001,$f^8(100110001)=f^7(0100)=f^6(0)=f^5(\varepsilon)=\varepsilon$,所以答案是 0。