P7809-01 序列
- 第一问
- 第二问
在练习ST的时候做了这题，但这其实算是一道思维题。
第一问
想了几个小时，假了几发思路没能想到点上，于是看题解。这道题其实就是要在求给定的区间内找出一个点i，使得点i左边的0的个数和点i右边的1的个数这两个数加起来最大。
到这里，已经知道要求区间的什么最值了，但这两个数的和要怎么求出来？自然想到要用前缀和。假设sum0[i]为从1到i的前缀上的0的个数，sum1[i]为从1到i的前缀上1的个数，那么上面所说的那两个数的和就是
sum0[i]−sum0[l−1]+sum1[r]−sum1[i]=(sum1[r]−sum0[l−1])+(sum0[i]−sum1[i])
对于固定的区间[l, r]，sum1[r]−sum0[l−1]的值是固定的。所以只要找出区间内最大的sum0[i]−sum1[i]。ST也就是用来存这个的。
需要注意的是，如果区间上所有的数都是1，区间的i其实应该选在l-1的位置，所以对于每个区间，应该找
maxi=l−1r(sum0[i]−sum1[i])
第二问
简单得很，代码里讲。
需要注意的是，（至少我的代码）这题不用快读不能满分。用了快读之后也需要注意局部性（将稀疏表的j放在前面）。为了便于查看，下面的代码是没有快读的，但考虑了局部性。
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
| #include <bits/stdc++.h>
using namespace std;
short a[5000005];
int st[27][5000005], sum0[5000005], sum1[5000005], pos0[5000005], pos1[5000005], n;
void ST_prework()
{
int i, j, t = log2(n);
for (i = 0; i <= n; i++)
st[0][i] = sum0[i] - sum1[i];
for (j = 1; j <= t; j++)
for (i = 0; i + (1 << j) - 1 <= n; i++)
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int query(int l, int r)
{
int k = log2(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
int main()
{
int i, q, l, r, o, max0, max1, r0, r1;
scanf("%d%d", &n, &q);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++)
{
sum0[i] = sum0[i - 1];
if (a[i] == 0)
{
sum0[i]++;
pos0[sum0[i]] = i;
}
}
for (i = 1; i <= n; i++)
{
sum1[i] = sum1[i - 1];
if (a[i] == 1)
{
sum1[i]++;
pos1[sum1[i]] = i;
}
}
ST_prework();
while (q--)
{
scanf("%d%d%d", &o, &l, &r);
if (o == 2)
{
if (pos1[sum1[r]] > l && sum0[pos1[sum1[r]]] > sum0[l - 1])
printf("2\n");
else
printf("1\n");
continue;
}
printf("%d\n", sum1[r] - sum0[l - 1] + query(l - 1, r));
}
return 0;
}
|