自动搬运

查看原文

来自洛谷，原作者为

	yuanzhiteng Barren As Resplendent Helius

搬运于2025-08-24 22:21:33，当前版本为作者最后更新于2023-07-29 16:32:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

一. 错误思路

拿到题后一头雾水......
容易想到的是二分 $t$，然后倒推模拟。
这种做法有两个错误。
$(1)$ 二分的前提：二分对象具有 单调性。
但是本题中的 $t$ 具有单调性吗？
换句话说，若对于 $t_1$ 不满足题意，$\forall t_2>t_1$ 都不满足题意吗？
稍微手玩一下会发现 $t$ 并没有单调性。
比如看下面这个例子：

3 3 1
- 0
+ 3
+ 6

若 $t=3$，它是不满足题意的。
但若 $t=4$，它却是满足题意的。
所以 不能二分 $t$ 。（注意不是不能二分，而是不能二分 $t$，下面会说）
$(2)$ 倒推真的可以吗？
我们知道，当给定一个序列和 $V_1$ 后，正推是很好推的。
但是倒推呢？
如果没有 $触底/触顶$ 机制还好说，可以倒推，但是如果有了这个机制呢？
由于状态 $i$ 是由状态 $i-1$ 得到，所以我们无法知道状态 $i-1$ 时是否触底/顶。
比如：倒推此时 $nowv=0,op=-$，无法确定上一个状态是 $1$ 还是 $0$。
所以倒推也是不行的。
当然如果你对于触底时随机选择，多跑几遍取 max 当我没说，脸好可以骗点分。

二. 题目分析

那怎么办？
俗话说：“OI 暴力始” 先考虑暴力如何做。
既然 $t$ 不能二分，那干脆直接枚举 $[0,maxt]$ 中的所有 $t$。
有了 $t$ 后还不够。
上面已经说了不能倒推。
所以只能正着推。
问题又来了，正着推缺条件—— $V_1$。
管他的，暴力枚举。
那么有了 $V_1$ 和 $t$ 后就能 $\mathcal{O}(n)$ 模拟得到相应的 $V_2$ 了。
如果对于 $t=maxt$ 仍然能满足题意，那么输出 infinity。
时间复杂度 $\mathcal{O}(nV_{max}\max(C_i))$。
好恐怖的复杂度。(* ￣▽￣* )
考虑优化。
首先，$t$ 是否需要枚举所有的 $t$？
发现不需要，只需要枚举 时间段 即可。
什么意思呢？
呐，比如说样例一。
对于 $t=2$ 和 $t=3$ 效果是一样的。
枚举的关键应该在于 操作序列状态的改变。
所以在样例一中只需要枚举 $t=1,4,5,6,8$。
这样便将 $t$ 的范围缩小到了 $\mathcal{O}(n)$。
其次，真的都不能二分吗？
发现 $V_1$ 可以二分。
感性地理解，当 $V_1$ 增加了，相当于“起点”上升了，但后面的过程一样，由于起点更高，终点自然也就不会更低。
具体地，设 $f(V_1)$ 表示 $V_1$ 经过操作序列后能得到的 $V_2$。
那么 $f(V_1)$ 是非严格单调递增的。
所以可以 $\mathcal{O}(\log n)$ 枚举 $V_1$。
所以优化后的时间复杂度为 $\mathcal{O}(n^2\log n)$。
有分，但不多。
再考虑去优化它。
时间复杂度的瓶颈在哪里呢？
二分 $V_1$ 是没有办法省去的，毕竟要正着推。
那......$t$ 呢？
好像也没法直接地省去。
没办法了吗？
难道......真的要在这里倒下了吗哦(* >﹏<* )？
换一种思考角度，既然没办法直接去掉时间复杂度，那能不能将它“拆”开呢？
换句话说，能不能先判断 $t$ 有无对应的 $V_1$ 符合题意，求出最大的 $t$ 后再去二分 $V_1$ 呢？
假设判断是至多 $\mathcal{O}(\log n)$ 的，那么时间复杂度就降为了 $\mathcal{O}(n\log n+logn)=\mathcal{O}(n\log n)$ 。
这不就可以通过了吗？
所以关键在于如何快速判断对于一个给定的 $t$ 是否存在合法的 $V_1$ 使之满足题意。
如何判断？
再次仔细观察题面：
如果当前操作成功，则
对于 $+$ 操作，音量 $x$ 会变为 $\min(V_{max},x+1)$；
对于 $-$ 操作，音量 $x$ 会变为 $\max(0,x-1)$；
欸，感觉来了。 (≧∇≦)
这不就是 $\min(c,\max(b,x+a))$ 复合函数的形式吗？
对于 $+$ 操作，即 $c=V_{max},b=0,a=1$；
对于 $-$ 操作，即 $c=V_{max},b=0,a=-1$；
对于不成功的操作，即 $c=V_{max},b=0,a=0$；
而且经验告诉我们，这个函数是可以复合的！！！
证明如下：

由于在网上翻遍了也没有对复合函数的详细证明，要么是“手玩一下”，要么是“易知”，要么是提都不提，但真的有这么容易吗？反正我是不会。
捣敲了老半天，终于搞出来了。
自己推的复合函数 $g(f(x))$ 推法：
令 $f(x)=\min(c_1,\max(b_1,x+a_1)),g(x)=\min(c_2,\max(b_2,x+a_2))$，则

$$\begin{aligned} g(f(x))&=\min(c_2,\max(b_2,\min(c_1,\max(b_1,x+a_1))+a_2)) \\ &=\min(c_2,\max(b_2,\min(a_2+c_1,\max(a_2+b_1,x+a_1+a_2)))) \end{aligned}$$

然后分类进行讨论：

(1) 若 $a_2+c_1<\max(a_2+b_1,x+a_1+a_2)$，则：

$$g(f(x))=\min(c_2,\max(b_2,a_2+c_1))$$

然后注意到有一个重要结论：

$$\min(a,\max(b,c))=\max(b,\min(a,c))$$

这个结论可以对 $a,b,c$ 大小关系分类去证明。
所以就可以继续化简：

$$g(f(x))=\max(b_2,\min(c_2,a_2+c_1))$$

（其实情况 $1$ 并不需要继续化简，但情况 $2$ 必须这样同样化简，所以先给出）
(2) 若 $a_2+c_1\ge \max(a_2+b_1,x+a_1+a_2)$，则：

$$\begin{aligned} g(f(x))&=\min(c_2,\max(b_2,\max(a_2+b_1,x+a_1+a_2)))\\ &=\min(c_2,\max(x+a_1+a_2,\max(b_2,a_2+b_1))) \\ &=\max(x+a_1+a_2,\min(c_2,\max(b_2,a_2+b_1))) \end{aligned}$$

因此才有：

$$f(g(x))=\min(\max(b_2,\min(c_2,a_2+c_1))\ ,\ \max(\min(c_2,\max(b_2,a_2+b_1)),x+(a_1+a_2))) $$

这个形式与 $\min(c,\max(b,x+a))$ 是吻合的。

告诉我，对于一段序列的复合函数如何维护？
线段树！
噫吁嚱，豁然开朗呼！
做法便明朗了：
令每一个操作的 $t_i=Time_{i}-Time_{i-1}$。
先将所有操作打入线段树，用线段树维护贡献。
然后判断 $V_2$ 是否落在 $f(V_1)$ 的值域中。
（因为 $V_1$ 的定义域不变，始终是 $[0,V_{max}]$）
如果是，那么说明所有操作均有效时可以，$t$ 可以无穷大，输出 infinity。
否则，将 $t_i$ 从大到小排序。
一个一个枚举 $nowtime=t_i$，将所有 $t=nowtime$ 的操作的贡献从线段树中单点修改去掉。
然后判断 $V_2$ 是否落在 $f(V_1)$ 的定义域中。
即判断 $V_2\ge tree[1].calc(0)\text{且}V_2\le tree[1].calc(V_{max})$ 是否成立。
如果成立，那么 $nowtime-1$ 即为 $t$ 的答案。
为什么要 $-1$ 呢？
因为此时的 $nowtime$ 表示所有 $\le nowtime$ 的操作均不合法，要使得 $t_i=nowtime$ 的操作不合法，就需要 $t<nowtime$，故应为 $nowtime-1$。
最后确定 $t$ 即确定操作序列的状态后，直接二分 $V_1$，判断 $tree[1].calc(V_1)$ 与 $V_2$ 的大小关系即可。
时间复杂度 $\mathcal{O}(n\log n)$。
嘛，还有一点就是，那个，操作 $1$ 一定是无效操作！！！
所以要忽略掉操作 $1$。
别踩坑了。
具体细节见代码。

三. 代码实现

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 1e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }

int n,Vmax,V2;
int Time[maxn],val[maxn];
struct Operation{
    int time,val,id;
}a[maxn];                       //存放操作序列
struct Segment{
    int a,b,c;                  //线段树维护函数min(c,max(b,x + a))
    int calc(int x){
        return min(c,max(b,x + a));
    }
}tree[maxn << 2];
inline int left(int x){
    return x << 1;
}
inline int right(int x){
    return x << 1 | 1;
}
inline void push_up(int p){
    int lson = left(p),rson = right(p);
    int a1 = tree[lson].a,b1 = tree[lson].b,c1 = tree[lson].c;
    int a2 = tree[rson].a,b2 = tree[rson].b,c2 = tree[rson].c;
    tree[p].c = max(b2,min(c2,c1 + a2));
    tree[p].b = min(c2,max(b2,b1 + a2));
    tree[p].a = a1 + a2;                        //这里的复合要手推一下,博客有详细证明
}
inline void build(int p,int l,int r){
    if(l == r){
        tree[p] = (Segment){val[l],0,Vmax};
        return;
    }
    int mid = (l + r) >> 1;
    build(left(p),l,mid);
    build(right(p),mid + 1,r);
    push_up(p);
}
inline void update(int p,int l,int r,int x){    //将操作x的贡献抹除掉
    if(l == r){
        tree[p] = (Segment){0,0,Vmax};
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)    update(left(p),l,mid,x);
    else update(right(p),mid + 1,r,x);
    push_up(p);
}
inline bool cmp(Operation x,Operation y){
    return x.time > y.time;
}
inline int get_V1(){        //由于复合函数对于f(V1)具有单调性,故在确定操作序列(即已经确定了t)后可以二分找V1
    int V1 = 0;
    int l = 0,r = Vmax,mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(tree[1].calc(mid) <= V2) V1 = mid,l = mid + 1;
        else r = mid - 1;
    }
    return V1;
}
int main(){

    read(n,Vmax,V2);
    for(int i=1;i<=n;i++){
        char c;
        cin >> c;
        if(c == '+')    val[i] = 1;
        else    val[i] = -1;
        read(Time[i]);
    }
    n--;                                    //将数组整体向左移了一格,至于为什么这么做嘛,第一步操作肯定是无效的
    for(int i=1;i<=n;i++){
        val[i] = val[i+1];                  //左移操作
        Time[i] = Time[i+1] - Time[i];      //由于t与间隔有关,所以只存t的阶段
        a[i] = (Operation){Time[i],val[i],i};
    }
    build(1,1,n);
    if(V2 >= tree[1].calc(0) && V2 <= tree[1].calc(Vmax)){      //所有操作都存在时满足(对于V1的值域[0,Vmax]经过复合函数后得到的值域包含了V2)那么t就是无穷解
        printf("infinity\n");
        return 0;
    }

    sort(a + 1,a + 1 + n,cmp);
    int i,j;
    for(i=1;i<=n;i=j){                      //从大到小枚举时间段t,并将操作一个一个从序列中减去,当V2恰好落在复合函数的值域中时,t最大,为nowtime-1(-1是因为要想让这些操作失效,必须<nowtime)
        int nowtime = a[i].time;
        for(j=i;a[j].time == a[i].time;j++)    //将所有这个时间段内的贡献抹去    
            update(1,1,n,a[j].id);
        if(V2 >= tree[1].calc(0) && V2 <= tree[1].calc(Vmax)){  //第一次满足时即为答案
            printf("%d %d\n",nowtime-1,get_V1());
            return 0;
        }
    }

    return 0;
}