一种差分解法思路

lr580 发表于 2年前 · 关联问题 猜数

因为有人问所以就顺手写成题解了,时间仓促排版不好看请见谅awa

设正确的数是y

那么准确次数为:

所有满足x > y的输入的x +

所有满足x < y的输入的x -

所有满足x = y的输入的x .

即对于特定的y,答案为:

(-无穷, y) 内 + 的数目

[y, y] 内 . 的数目

(y, +无穷) 内 - 的数目

那么:

当输入一个 x + 时,根据上文即 y < x ,所以

所有(-无穷, x) 的 y 值的准确次数加一

当输入一个 x - 时,根据上文即 y > x ,所以

所有(x, +无穷) 的 y 值的准确次数加一

当输入一个 x . 时,根据上文即 y = x ,所以

所有 [x,x] 的 y 值准确次数加一

根据上述规则,一段区间内的 y 的准确次数会不同时,当且仅当这个区间里出现过 x ,也就是说 x 是导致 y 区间内准确次数变化的原因,当一个区间内没有输入的 x 时,这个区间内所有 y 的准确次数相同

也就是说只要枚举 x 的所有取值和正负无穷,就可以得到所有不同的准确次数

所以解法是:

设正负无穷为 x 取不到的值,依次为2e9,-2e9

定义区间单值的意义是 y 取该值时,准确次数为多少:

每输入一个 x ,

若是 x + ,将区间 [-2e9,x) 加一

若是 x - ,将区间 (x, 2e9] 加一

若是 x . ,将区间 [x,x] 加一

最后求区间最值即可。

区间加法的时间复杂度高,由于有多次区间加法和最后一次区间查询,可以用差分优化,每次区间[a,b]加法在两点a,b+1分别作加减标记,最后查询之前进行前缀和即可,前缀和后得到原区间,可以求出区间最值

由于 x 范围过大,使用 map 离散化来存

参考代码如下:

#include <bits/stdc++.h> using namespace std; typedef int ll; #define sc(x) scanf("%d", &x) #define il inline map<ll, ll> s; ll r, n, v, mx; char c; signed main() { sc(n); while (n--) { scanf("%d %c", &v, &c); if (c == '+') ++s[-2e9], --s[v]; else if (c == '-') ++s[v + 1], --s[2e9]; else ++s[v], --s[v + 1]; } for (auto i : s) { r += i.second; mx = max(mx, r); } printf("%d", mx); return 0; }