01 游戏

题目描述

有一个长度为 $n$ 的 $01$ 串 $s$ ，每次给定一个子串 $s[l,r]$ 。

对一个长度为 $n’$ 的 01 串 $s'$，你可以进行操作：

先选择一个操作集合 $U\subseteq \left\{0,1,\cdots,n'\right\}(可以是空集)$ ，然后每次选择一个最大的 $x\in U$ 并将其从 $U$ 中删去，然后将 $s'[1,x]$ 按位取反，将 $s'[x+1,n']$ 翻转。 注意 $s'[1,x]$ 和 $s'[x+1,n']$ 都可以为空子串。

定义一个字符串 $s$ 的价值为其满足相邻位不同的最长子段长度。

现在要求你对于每次给定的子串都挑选一个操作集合，最大化操作后子串的价值，你只需要输出价值。

输入格式

给出一行 $n ,q$ ，代表字符串长度，询问次数

第 $2$ 到第 $n+1$ 行，每行两个正整数 $l,r$ ，代表询问的子串 $s[l,r]$

输出格式

输出 $q$ 行，分别为每个询问子串操作后得到的最大价值。

输入输出样例

输入 1

5 3
01111
1 2
1 5
2 3

输出 1

2
3
2

输入 2

10 5
1001000101
1 7
2 6
4 9
1 10
5 8

输出 2

5
4
5 
7
2

数据范围

SubTask1 (20pts) 1~5: $n\le10 , q\le10$

SubTask2 (30pts) 6~10: $n\le5000 , q\le5000$

SubTask3 (20pts) 11~15: $n\le500000 , q=1 , l=1 , r= n$

SubTask4 (30pts) 16~20: $n\le500000 , q\le500000$