题目描述

难度:[蓝]提高+/省选-

大家都知道喷泉吧？现在有一个喷泉由$N$个圆盘组成，从上到下以此编号为$1$∼$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$行每行一个整数代表询问的答案。

输入样例

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

输出样例

5
0
5
4
2

算法

倍增+二分

这是今天进阶版的茶，如果每个询问不是相互独立的，就和今天茶的解法基本一样，只要用单调栈预处理出每个盘子$i$的右边第一个直径大于自己的位置$down[i]$就可以了。唯一的区别是并查集合并$i$和$find(down[i])$两个节点，而不是$i$和$find(i+1)$。但遗憾的是，本题的询问都是相互独立的，如果用并查集的话还需要进行撤回操作，时间复杂度太高了。

我们可以采用倍增来预处理出两个信息$p$和$sum$，$p[i][j]$表示盘子$i$向后走$2^j$步所能到达的盘子编号，$sum[i][j]$表示盘子$i$向后走$2^j$步所经过盘子的总体积（不包括盘子$i$）。

然后对于每个询问，我们二分找出$R_i$往后走多少步会使得路径上所有盘子的体积刚好大于$V_i$，那个盘子就是$V_i$体积的水倒进盘子$R_i$后最终流向的盘子。

复杂度分析

时间复杂度

倍增预处理出$p$的时间复杂度为$O(nlog_2n)$。之后对于每个询问$i$，需要先二分答案找到$R_i$走多少步可以使得路径上盘子的容积大于$V_i$，时间复杂度为$O((log_2n)^2)$，一个$log$是二分，还有一个$log$是$check$（需要用二进制来凑给定的步数），所以处理所有询问的时间复杂度为$O(m(log_2n)^2)$。

综上，算法整体的时间复杂度为$O(nlog_2n+m(log_2n)^2)$。

空间复杂度

除去题目输入的数组，空间消耗主要是$p$和$sum$两个数组，额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int n, q, d[N], c[N], p[N][18], sum[N][18];

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &d[i], &c[i]);
        p[i][0] = n + 1;
        sum[i][0] = 0;
    }
    stack<int> stk;
    for(int i = 1; i <= n; i++) {
        while(!stk.empty() && d[stk.top()] < d[i]) {
            p[stk.top()][0] = i;
            sum[stk.top()][0] = c[i];
            stk.pop();
        }
        stk.push(i);
    }
    for(int j = 0; j < 17; j++) {
        for(int i = 1; i <= n; i++) {
            p[i][j + 1] = p[p[i][j]][j];
            sum[i][j + 1] = sum[i][j] + sum[p[i][j]][j];
        }
    }

    function<int(int, int)> check = [&](int src, int k) {
        int x = src, s = c[src];
        for(int j = 0; j <= 17; j++) {
            if(k>>j&1) {
                s += sum[x][j];
                x = p[x][j];
            }
        }
        return s;
    };

    for(int index = 1; index <= q; index++) {
        int ri, vi;
        scanf("%d%d", &ri, &vi);
        if(c[ri] >= vi) {
            printf("%d\n", ri);
        }else {
            int l = 1, r = n;
            while(l < r) {
                int mid = l + r >> 1;
                if(check(ri, mid) >= vi) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            int k = r, x = ri;
            for(int j = 0; j <= 17; j++) {
                if(k>>j&1) {
                    x = p[x][j];
                }
            }
            if(x == n + 1) {
                puts("0");
            }else {
                printf("%d\n", x);
            }
        }
    }
    return 0;
}