P7167 [eJOI 2020] Fountain (Day1)

题目描述

大家都知道喷泉吧？现在有一个喷泉由 $N$ 个圆盘组成，从上到下以此编号为 $1\sim N$，第 $i$ 个喷泉的直径为 $D_i$，容量为 $C_i$，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径大于这个圆盘的圆盘里。如果下面没有满足要求的圆盘，水就会流到喷泉下的水池里。

现在给定 $Q$ 组询问，每一组询问这么描述：

• 向第 $R_i$ 个圆盘里倒入 $V_i$ 的水，求水最后会流到哪一个圆盘停止。

如果最终流入了水池里，那么输出 $0$。

注意，每个询问互不影响。

输入格式

第一行两个整数 $N,Q$ 代表圆盘数和询问数。
接下来 $N$ 行每行两个整数 $D_i,C_i$ 代表一个圆盘。
接下来 $Q$ 行每行两个整数 $R_i,V_i$ 代表一个询问。

输出格式

$Q$ 行每行一个整数代表询问的答案。

输入输出样例 #1

输入 #1

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

输出 #1

5
0
5
4
2

说明/提示

样例 1 解释

前两个询问的解释如下图所示：

因为每个询问互不影响，对于第三个询问，第 $5$ 个圆盘里的水不会溢出。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（30 pts）：$N\le 1000$，$Q\le 2000$。
• Subtask 2（30 pts）：$D_i$ 为严格单调递增序列。
• Subtask 3（40 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $2\le N\le 10^5$。
• $1\le Q\le 2\times 10^5$。
• $1\le C_i\le 1000$。
• $1\le D_i,V_i\le 10^9$。
• $1\le R_i\le N$。

说明

翻译自 eJOI 2020 Day1 A Fountain。

这道题我个人认为是一道很好的题，解法不算特别明显 （个人认为） 但只要想到就会觉得很简单。

首先，我们可以从圆盘的性质入手：我们发现，如果某个圆盘的水会溢出，那么多出的水会流向它下面第一个半径比它大的圆盘。这让你想到了什么？

没错，它下面第一个+比它大，这不就是单调栈吗？

我们把水池看作第$N+1$个点，它可以看作是半径与容量无限大的圆盘，因此设它为一个极大值，保证它是半径最大的，接下来上单调栈代码：

d[n+1]=1e10;
for(int i=1;i<=n+1;i++){
    while((!st.empty())&&d[i]>d[st.top()]){
        //………………之后要写的操作
        st.pop();
    }
    st.push(i);
}

所以，目前这道题最朴素的想法就是对于每一个$R_i$，都进行一次单调栈的操作，找到以$R_i$为起点的最长上升子序列，然后模拟出第一个总容量不小于$V_i$时的位置。

但想也不用想，$2\le N\le 10^5$，$1\le Q\le 2\times 10^5$，肯定会超时。

那么我们有没有优化方法呢？有的兄弟，有的。

圆盘的性质我们还没发掘完呢！刚才说了，每一个圆盘中溢出的水都会流向它下面第一个半径比它大的圆盘，也就是说，每一个圆盘中溢出的水都只会流向一个确定的圆盘。反过来，每一个圆盘都可能会接收它上面若干个半径比它小的圆盘溢出的水。

如果这还不够明显，我们再想想那个水池，水池其实是给所有圆盘兜底的，它相当于一个“超级节点”，不论水有多少，最多只能流向它。这是否让你想起了树中的“根节点”？

没错！这居然是一棵树！对于每一个圆盘来说，它下面第一个半径比它大的圆盘就是它的父节点（注意不是子节点，如上所述，一个圆盘只溢出水给另一个圆盘，但一个圆盘却能接受若干个圆盘溢出的水，正如在树上，一个子结点只有一个父节点，但一个父节点却会有若干个子节点）。

因此，我们可以通过单调栈建树，那么单调栈的代码可以补全了：

d[n+1]=1e10;
for(int i=1;i<=n+1;i++){
    while((!st.empty())&&d[i]>d[st.top()]){
        l[i].push_back(st.top());
        st.pop();
    }
    st.push(i);
}

当然，这样做只避免了对于每个询问都进行单调栈的操作，对于不超时，这样显然还是不够的，那有没有方法能够让我们快速找到答案呢？有的兄弟，有的。

你可能会想到二分，但这样写比较麻烦（至少我没想到怎么写不费脑子），我么可以换个思路，用倍增的方法解决问题。

对于$c[i][j]$，表示为第$i$个节点包括自己在内的$2^j$个节点的和，对于$f[i][j]$，表示第$i$个节点向上走$2^j$个节点到达的节点。

注意：这两个数组终点编号是不一样的，举个例子：

1->2->3->4->5

设点的权值是它的编号，那么，$c[5][2]=5+4+3+2=14$，而$f[5][2]=1$。

现在我们可以直接套用模板，写出深搜代码：

void dfs(int t){
    for(int i=1;(1<<i)<=b[t];i++){
        f[t][i]=f[f[t][i-1]][i-1];
        c[t][i]=c[f[t][i-1]][i-1]+c[t][i-1];
    }
    for(int i=0;i<l[t].size();i++){
        if(f[t][0]!=l[t][i]){
            f[l[t][i]][0]=t;
            b[l[t][i]]=b[t]+1;
            dfs(l[t][i]);
        }
    }
}

通过倍增的处理，我们可以快速地求经过的所有圆盘的容量和。接下来我们考虑如何找到那个恰好不会溢出的那个圆盘。

怎么做到“恰好”呢？其实很简单，当你发现$c[i][j]>=V$但$c[i][j-1]<V$时，向上走$2^{j-1}$，所有能走完的走完以后的点即为答案，注意：在最近公共祖先中，我们输出的可能是$f[i][0]$这样的东西，但最近公共祖先中的$i$指的是最远非公共祖先，而我们这个算法算出的的$i$却是最近不溢出点，所以直接输出结果就好 （写的时候因为这点卡了好久） 。

输出部分代码：

for(int i=1;i<=q;i++){
    cin>>r>>v;
    long long ss=0;
    for(int j=17;j>=1;j--){
        if(ss+c[r][j]>=v&&ss+c[r][j-1]<v){
            ss+=c[r][j-1];
            r=f[r][j-1];
         
    }
    if(r==n+1){
        cout<<0;
    }else{
        cout<<r;
    }
    cout<<endl;
}

然后几个小细节注意一下：$c[i][j]$在没有具体数值时要赋予为一个极大值，防止判断出错，其次就是$c[i][j]$要开$long$ $long$类型的，因为虽然$1\le V_i\le 10^9$,但最多是$N$个$10^9$，会爆$int$（虽然我实测不开64位好像也能过） ，最后，我们原来设水池为$N+1$号点，但题目却要求将水池输出为$0$，因此需要特判一下。

上AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,q;
long long d[100005],r,v,f[100005][20],b[100005],c[100005][20];
vector <int> l[100005];
stack <int> st;
void dfs(int t){
    for(int i=1;(1<<i)<=b[t];i++){
        f[t][i]=f[f[t][i-1]][i-1];
        c[t][i]=c[f[t][i-1]][i-1]+c[t][i-1];
    }
    for(int i=0;i<l[t].size();i++){
        if(f[t][0]!=l[t][i]){
            f[l[t][i]][0]=t;
            b[l[t][i]]=b[t]+1;
            dfs(l[t][i]);
        }
    }
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>d[i]>>c[i][0];
    }
    c[n+1][0]=1e17;
    d[n+1]=1e10;
    for(int i=1;i<=n+1;i++){
        while((!st.empty())&&d[i]>d[st.top()]){
            l[i].push_back(st.top());
            st.pop();
        }
        st.push(i);
    }
    b[n+1]=1;
    dfs(n+1);
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<18;j++){
            if(!c[i][j]){
                c[i][j]=1e18;
            }
        }
    }
    for(int i=1;i<=q;i++){
        cin>>r>>v;
        long long ss=0;
        for(int j=17;j>=1;j--){
            if(ss+c[r][j]>=v&&ss+c[r][j-1]<v){
                ss+=c[r][j-1];
                r=f[r][j-1];
            }
        }
        if(r==n+1){
            cout<<0;
        }else{
            cout<<r;
        }
        cout<<endl;
    }
    return 0;
}

我的第一篇题解就这样完 （水） 成 （完） 了！！！