1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define INF (0x7ffffff)
using namespace std;
struct node
{
int le, ri, minfr, minsu, minz;
}b[MAXN << 2];
int fr[MAXN], su[MAXN], n, ans, minpre, a[MAXN], q;
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].minfr = fr[le];
b[dq].minsu = su[le];
b[dq].minz = INF;
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
b[dq].minfr = min(b[LS(dq)].minfr, b[RS(dq)].minfr);
b[dq].minsu = min(b[LS(dq)].minsu, b[RS(dq)].minsu);
b[dq].minz = min(min(b[LS(dq)].minz, b[RS(dq)].minz), b[RS(dq)].minsu + b[LS(dq)].minfr);
}
void cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
ans = min(ans, b[dq].minz);
ans = min(ans, b[dq].minsu + minpre);
minpre = min(minpre, b[dq].minfr);
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
cx(LS(dq), le, ri);
else if (le > mi)
cx(RS(dq), le, ri);
else
cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1, srx; i <= n; i++)
scanf("%1d", &srx), a[i + 1] = (srx ? -1 : 1);
for (int i = 2; i <= n + 1; i++)
fr[i] = fr[i - 1] + a[i];
for (int i = n + 1; i > 1; i--)
su[i] = su[i + 1] + a[i];
js(1, 1, n + 2);
for (int i = 1, srl, srr; i <= q; i++)
{
scanf("%d%d", &srl, &srr);
srr += 2;
ans = minpre = INF;
cx(1, srl, srr);
printf("%d\n", fr[srl] + su[srr] - ans);
}
return 0;
}
|