#P18684. Not Another Range Query Problem

    ID: 18020 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-查询排序链表树状数组懒标记线段树线段树上二分不变量分析同时事件分阶段处理增量维护

Not Another Range Query Problem

Not Another Range Query Problem

题目描述

都什么年代了,你还在做传统的区间查询题?

小青鱼是区间查询题的头号爱好者,他想找到 3202 年最好的区间查询题。幸运的是,他发现了一道二进制字符串问题。他很喜欢二进制字符串,因为它们曾在 2202 年带来过 Best Problem。

对于长度为 nn 的二进制字符串 s=s1s2⋯sns=s_1s_2\cdots s_n,定义 L(s)L(s) 为所有满足下列条件的位置 ii(1≤i≤n1\le i\le n)组成的集合:i=1i=1,或者 si≠si−1s_i\ne s_{i-1}。

例如,L(0011100)={1,3,6}L(0011100)=\{1,3,6\},L(00101101)={1,3,4,5,7,8}L(00101101)=\{1,3,4,5,7,8\},L(000)={1}L(000)=\{1\}。特别地,若 s=εs=\varepsilon 是空串,则 L(ε)=∅L(\varepsilon)=\varnothing。

令 f(s)f(s) 为从 ss 中同时删除所有下标属于 L(s)L(s) 的字符后得到的字符串。下表来自原 PDF,下划线表示本次被删除的字符:

原题的删除字符示例表

表中的结果依次为:f(0011100)=0110f(0011100)=0110,f(00101101)=01f(00101101)=01,f(000)=00f(000)=00,f(01)=εf(01)=\varepsilon,f(ε)=εf(\varepsilon)=\varepsilon。

小青鱼发现的问题要求求出 fk(s)f^k(s) 的长度,其中

$$f^k(s)=\begin{cases}f^{k-1}(f(s)),&k\ge1,\\s,&k=0.\end{cases}$$

小青鱼希望将它变为区间查询问题。因此,他给你字符串 s=s1s2⋯sns=s_1s_2\cdots s_n 和 qq 次查询。每次给出三个整数 l,r,kl,r,k,你需要输出 fk(s[l⋯r])f^k(s[l\cdots r]) 的长度,其中 s[l⋯r]=slsl+1⋯srs[l\cdots r]=s_ls_{l+1}\cdots s_r。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤5×1051\le n,q\le5\times10^5),分别表示字符串长度和查询次数。

第二行包含一个二进制字符串 ss(∣s∣=n|s|=n,si∈{0,1}s_i\in\{0,1\})。

接下来 qq 行,每行描述一次查询,包含三个整数 l,r,kl,r,k(1≤l≤r≤n1\le l\le r\le n,0≤k≤n0\le k\le n)。

输出格式

对于每次查询,输出一行一个整数,表示 fk(s[l⋯r])f^k(s[l\cdots 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

样例解释

  1. s[2⋯5]=0011s[2\cdots5]=0011,f(0011)=01f(0011)=01,所以答案是 22。
  2. s[3⋯6]=0110s[3\cdots6]=0110,f(0110)=1f(0110)=1,所以答案是 11。
  3. s[4⋯8]=11000s[4\cdots8]=11000,f2(11000)=f(100)=0f^2(11000)=f(100)=0,所以答案是 11。
  4. s[2⋯7]=001100s[2\cdots7]=001100,f(001100)=010f(001100)=010,所以答案是 33。
  5. s[1⋯9]=100110001s[1\cdots9]=100110001,f(100110001)=0100f(100110001)=0100,所以答案是 44。
  6. s[1⋯9]=100110001s[1\cdots9]=100110001,f0(100110001)=100110001f^0(100110001)=100110001,所以答案是 99。
  7. s[1⋯9]=100110001s[1\cdots9]=100110001,$f^8(100110001)=f^7(0100)=f^6(0)=f^5(\varepsilon)=\varepsilon$,所以答案是 00。