Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Илья болон хүсэлт
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ильягийн найзууд бүгдээрээ шалгалтан дээр бие биедээ туслахыг хүсдэг. IT-гийн шалгалтан дээр дараах асуудал гарж ирсэн.
Бид нарт $s = s_1s_2... s_n$ ($n$ урттай ), зөвхөн "." болон "#" -с тогтсон тэмдэгт мөр өгөгдөнө. Бидэнд $m$ ширхэг хүсэлт өгөгдөнө. Хүсэлт бүр нЬ $l_i$ $r_i$ $(1 ≤ li < ri ≤ n)$ гэсэн хоёр бүхэл тооноос тогтоно. Зэрэгцэж суусан хоёр ижил вариант авсан хүүхдүүд хоорондоо туслах боломжтой өөрөөр хэлбэл вариантууд $s_i == s_i + 1$ $i(l_i ≤ i < r_i)$ бол нэгэндээ туслаж болно.
$l$-с $r$ завсарт нийт хэдэн хүүхэд нэгэндээ туслаж болохыг тооцоолно уу.
Оролт
Эхний мөрөнд $n (2 ≤ n ≤ 10^5)$ урттай $s$ тэмдэгт мөр өгөгдөнө. Зөвхөн $"."$ болон $"#"$ тэмдэгтээс тогтсон байна.
Дараагийн мөрөнд нийт хүсэлтийн тоо $m (1 ≤ m ≤ 10^5) $ өгөгдөнө. Хүсэлт бүрийн хувьд $l , r(1 ≤ l_i < r_i ≤ n).$ хоёр бүхэл тоо өгөгдөнө.
Гаралт
Хүсэлт бүрийн хувьд өгөгдсөн дараалалаар харгалзах утгыг хэвлэ.
Орчуулсан: Хүрэлцоож
Жишээ тэстүүд
Оролт
...... 4 3 4 2 3 1 6 2 6
Гаралт
1 1 5 4
Оролт
#..### 5 1 3 5 6 1 5 3 6 3 4
Гаралт
1 1 2 2 0