[CEOI2010 day2] mp3player（线段树维护min-max复合函数，转化）
yuanzhiteng
·
·
题解
题目链接
一. 错误思路
拿到题后一头雾水......
容易想到的是二分 t，然后倒推模拟。
这种做法有两个错误。
但是本题中的 $t$ 具有单调性吗？
换句话说，若对于 $t_1$ **不**满足题意，$\forall t_2>t_1$ 都**不**满足题意吗？
稍微手玩一下会发现 $t$ 并没有单调性。
比如看下面这个例子：
```cpp
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$。
别踩坑了。
具体细节见代码。
****
### 三. 代码实现
```cpp
#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;
}
```