因为有人问所以就顺手写成题解了,时间仓促排版不好看请见谅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;
}