幽默的世界
洛谷十月月赛 幽默的世界
题目描述
给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，定义 $a$ 的一个连续子序列 $a_l,a_{l+1},\cdots,a_r$ 是幽默的，当且仅当：
- $\sum\limits_{i=l}^ra_i>0$；
- 对于所有 $l\le x\le y<r$，满足 $\sum\limits_{i=x}^y a_i\le 0$。
$q$ 次询问，每次给定两个整数 $l,r$，查询满足以下条件的数对 $(l’,r’)$ 个数：
- $l\le l’\le r’\le r$；
- 连续子序列 $a_{l’},a_{l’+1},\cdots a_{r’}$ 是幽默的。
输入格式
第一行输入两个整数 $n,q$。
接下来一行输入 $n$ 个整数，第 $i$ 个整数代表 $a_i$。
接下来 $q$ 行，每行输入两个整数 $l,r$，代表一次询问。
输出格式
对于每组询问，输出一行一个整数，代表答案。
样例输入
1 | 7 6 |
样例输出
1 | 1 |
对于所有数据，保证 $1\le n,q\le 2\times 10^5$，$1\le l\le r\le n$，$|a_i|\le 10^9$。
子任务
| # | 特殊性质 | 分值 |
|---|---|---|
| 0 | 样例 | 0 |
| 1 | $n,q\le 50$ | 15 |
| 2 | $n,q\le 3\times 10^3$ | 20 |
| 3 | 对于所有询问，$r=n$ | 15 |
| 4 | 对于所有询问，$l=1$ | 15 |
| 5 | - | 35 |
不算难的一道题目，但是题目的描述过于抽象导致我差几十分钟写对它…
35pts：
读懂题目之后可以发现其实一个正数一定是一个幽默的数，那么再继续考虑可以发现，如果一个子序列长度大于1那么它的右边界一定是正数，并且有且只有一个正数，因为其他位置的正数都不会满足第二个要求，同时为了满足第一个要求，这个子序列的元素之和必定大于0，因此可以想到一种暴力的解法：定义一个指针先指向右边界，找到每次查询中最靠近右边界的正数，从这个正数开始找最长的满足第一个要求且不包含其他正数的子序列，多长就有多少个满足条件的子序列，反复去找直到指针指到左边界为止。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
using namespace std;
int n, q, a[N];
signed main() {
//freopen("input.txt", "r", stdin);
//freopen("stand.txt", "w", stdout);
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
a[n+1] = 0;
for (int i = 1, l, r; i <= q; ++i) {
int ans = 0;
cin >> l >> r;
ll sum = 0;
for (int j = r,pPos = r; j >= l; --j) {
if (sum + a[j] > 0) {
ans++;
if (pPos != j && a[j]>0)sum = 0;
sum += a[j];
} else {
while (a[j] <= 0 && j >= l)--j;
pPos = j;
++j;
sum = 0;
}
}
cout << ans << endl;
}
return 0;
}
可以证明这个做法是正确的，但是由于复杂度过高会超时。
100pts：
观察超时代码，可以发现主要的时间浪费在查询的遍历上，那么需要优化查询速度，至少要优化到O(logn)级别的复杂度，那么这个范围内可以接受的算法显然是二分，然后就往单调性方面去想，设左右边界为L,R，如果预处理出所有的正数下标，存在positive数组中那么显然这个下标是递增的，可以用二分查找，然后可以在O(logn)级别查到第一个下标小于等于R的正数下标r和第一个下标大于等于L的正数下标l，那么如果遍历一遍预处理出每个正数对应的最大的子序列，那么只需要计算sum[r] - sum[l] + min(positive[l] - L + 1, sum[l] - sum[l - 1])就可以不重不漏的查询出区间[L,R]内幽默的序列个数，但是还有个问题像下面这个数据就会输出负的数1
2
35 1
5 -3 1 3 0
5 5
原因很简单这时候r<l因为这个区间内没有正数，所以对于这种情况要将它的值取为0，合起来的表达式就是：
max(0ll, sum[r] - sum[l] + min(positive[l] - L + 1, sum[l] - sum[l - 1]))
1 |
|
总体来说不算难，比赛的时候由于用vector存正数，将前缀和数组从0开始赋值导致加了很多在0的时候的特判，导致在最后没调出来，比完了重构了代码就写出来了。其实对于这种题目，已经做出它的暴力版本然后发现正解出错而找不到bug的时候就应该考虑对拍，这道题的对拍不复杂，也是通过对拍在补题的时候发现了输出为负数的情况。
对拍代码：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
using namespace std;
void build(int T) {
ofstream fout("input.txt");
int n = random(1,10),q = random(1,3);
cout<<n<<' '<<q<<endl;
fout<<n<<' '<<q<<endl;
for(int i = 1,t;i<=n;++i){
t = random(-5,5);
cout<<t<<' ';
fout<<t<<' ';
}
cout<<endl;
fout<<endl;
for(int i = 1,l,r;i<=q;++i){
l = random(1,n);
r = random(l,n);
cout<<l<<' '<<r<<endl;
fout<<l<<' '<<r<<endl;
}
fout.close();
}
void create_dataset() {
int n = random(2,100);
int t = 1;
while (t--) build(n);
}
bool work() {
create_dataset();
system("stand.exe < input.txt");
system("my.exe < input.txt");
return system("fc stand.txt my.txt");
}
void dp(int tot) {
for (int i = 1; i <= tot; i++) {
cout << "test" << i << ":" << endl;
if(work()) {
cout << "WrongAnswer\n";
getchar();
}
}
}
int main() {
srand(time(nullptr));
dp(256);
cout << "Done";
return 0;
}
这道题充分说明了前缀和不要以0下标为开头不然在二分的时候要做一堆的判断血压容易上来…