题解：P6520 [CEOI2010 day2] mp3player

思路

考虑初始音量 x，如果 x 在某次操作后超过 Vmax，显然没有用处；同理如果小于 0，也没有用处。然后就用线段树维护当前区间有用的初始音量范围。然后求一下答案即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define M 300005
using namespace std;
int n, m, gol, pos[N], lf[M], rg[M], icr[M];
struct node {
    int x, y;
    bool k;
} a[N];
bool cmp(const node &u, const node &v) {
    return u.x < v.x;
}
void build(int k, int l, int r) {
    rg[k] = m;
    if (l == r) {
        // 将该位置对应的线段树节点编号记录在pos数组中
        pos[l] = k;
        return;
    }
    int mid = (l + r) >> 1;
    // 递归构建左子树
    build(k << 1, l, mid);
    // 递归构建右子树
    build(k << 1 | 1, mid + 1, r);
}
int main() {
    scanf("%d%d%d", &n, &m, &gol);
    n--;
    // 读取第一个操作的字符（'+'或'-'）和对应的时间值
    int i, k, x, y;
    char cr = getchar();
    while (cr!= '-' && cr!= '+')
        cr = getchar();
    scanf("%d", &x);
    // 循环读取后续的操作信息，构建操作节点数组a
    for (i = 1; i <= n; i++, x = y) {
        // 读取操作字符（'+'或'-'），跳过不是操作字符的输入
        cr = getchar();
        while (cr!= '-' && cr!= '+')
            cr = getchar();
        // 根据读取的操作字符确定k的值，true表示'+'操作，false表示'-'操作
        a[i].k = (cr == '+');
        // 读取本次操作与上一次操作的时间间隔对应的时间值
        scanf("%d", &y);
        a[i].x = y - x;
        a[i].y = i;
    }
    // 对操作节点数组a按照操作时间间隔x进行排序
    sort(a + 1, a + n + 1, cmp);
    // 构建线段树，根节点编号为1，初始区间为[1, n]
    build(1, 1, n);
    int ans1 = 1, ans2 = gol;
    for (i = 1; i <= n; i++) {
        // 如果当前操作是增加音量操作（'+'）
        if (a[i].k) {
            // 找到当前操作对应的线段树节点编号k
            k = pos[a[i].y];
            // 减少当前节点表示区间的右端点值
            rg[k]--;
            // 增加当前节点的增减量值
            icr[k]++;
        }
        // 如果当前操作是降低音量操作（'-'）
        else {
            k = pos[a[i].y];
            // 增加当前节点表示区间的左端点值
            lf[k]++;
            // 减少当前节点的增减量值
            icr[k]--;
        }
        // 向上更新线段树节点信息
        for (k >>= 1; k; k >>= 1) {
            // 更新当前节点的左端点值，取左右子树左端点值中的较大值
            lf[k] = max(lf[k << 1], lf[k << 1 | 1] - icr[k << 1]);
            // 更新当前节点的右端点值，取左右子树右端点值中的较小值
            rg[k] = min(rg[k << 1], rg[k << 1 | 1] - icr[k << 1]);

            // 如果当前节点的左端点值小于等于右端点值
            if (lf[k] <= rg[k])
                // 更新当前节点的增减量值，为左右子树增减量值之和
                icr[k] = icr[k << 1] + icr[k << 1 | 1];
            else
                // 如果右子树的右端点值加上其增减量值小于左子树的左端点值
                if (rg[k << 1] + icr[k << 1] < lf[k << 1 | 1]) {
                    // 将当前节点的左右端点值和增减量值都设置为左子树的左端点值和增减量值
                    lf[k] = rg[k] = lf[k << 1 | 1];
                    icr[k] = icr[k << 1 | 1];
                } else {
                    // 将当前节点的左右端点值和增减量值都设置为右子树的右端点值和增减量值
                    lf[k] = rg[k] = rg[k << 1 | 1];
                    icr[k] = icr[k << 1 | 1];
                }
        }
        // 如果当前是最后一个操作或者下一个操作的时间间隔与当前操作不同
        if (i == n || a[i].x!= a[i + 1].x) {
            // 如果当前节点的左端点值加上其增减量值小于等于目标值gol，且目标值gol小于当前节点的右端点值加上其增减量值
            if (lf[1] + icr[1] <= gol && gol < rg[1] + icr[1]) {
                // 更新答案变量ans1为当前操作序号加1
                ans1 = i + 1;
                // 更新答案变量ans2为目标值gol减去当前节点的增减量值
                ans2 = gol - icr[1];
            } else if (rg[1] + icr[1] == gol) {
                // 如果当前节点的右端点值加上其增减量值等于目标值gol
                ans1 = i + 1;
                // 将答案变量ans2设置为m
                ans2 = m;
            }
        }
    }
    if (ans1 > n)
        puts("infinity");
    else
        printf("%d %d\n", a[ans1].x - 1, ans2);
    return 0;
}