P2471 降雨量

降雨量：不完整信息下的三值判定

问题

P2471 降雨量
已知部分年份的降雨量。对每个 $Y<X$，判断“$X$ 年是自 $Y$ 年以来降雨量最多的”必真、必假，还是可能成立。

数据规模：$n\le 5\times10^4$，$m\le10^4$，年份和降雨量均可达 $10^9$。

这句话要求 $r_{X} \le r_{Y}$，并且对于任意 $Y<Z<X$，都有 $r_Z < r_X$。但是在实际操作之后，发现问题最麻烦的是，部分年份可能没有记录。

所以整理本题的判定思路：

若是已知信息产生矛盾 $\to$ false。
没有矛盾，且 $Y \to X$ 的每一年都已知 $\to$ true。
其余情况 $\to$ maybe。

由于年份已经按升序给出，所以直接在 year[] 上二分即可，不需要另外开一个 map。lower_bound 可以同时判断端点是否已知，并定位 ST 表中的连续下标；upper_bound(Y) 与 lower_bound(X)-1 则给出严格位于 $Y,X$ 之间的已知年份。

设这些中间记录的最大降雨量为 $mx$。

1. $Y,X$ 都已知时，若 $r_X>r_Y$，端点条件直接矛盾；
2. $X$ 已知时，若 $mx\ge r_X$，中间条件直接矛盾；
3. $X$ 未知而 $Y$ 已知时，需要为 $X$ 选择一个降雨量，使 $mx<r_X\le r_Y$，若 $mx\ge r_Y$，这个区间中不存在合法取值，因此仍然是 false。

只有不存在上述矛盾，并且 $Y,X$ 均已知、已知记录下标差等于年份差时，才能说明中间没有缺失年份，从而输出 true；否则未知年份仍可能改变结论，只能输出 maybe。

注：使用 map 时会产生问题，因为 mp[year] 会给未知年份自动插入值 $0$，破坏“该年份是否已知”这一关键信息。

ST 表只维护已知降雨量的区间最大值。预处理复杂度为 $O(n\log n)$，每次询问进行二分和 $O(1)$ RMQ，复杂度为 $O(\log n)$。

▶

P2471

struct ST {
/* ======================================== */
int st[maxn][maxlg], lg2[maxn];
void init_lg( int N ) {
    lg2[1] = 0;
    for( int i = 2; i <= N; ++ i ) lg2[i] = lg2[i >> 1] + 1;
}
void init( int N, int val[] ) {
    init_lg( N );
    for( int i = 1; i <= N; ++ i ) st[i][0] = val[i];
    for( int j = 1; ( 1 << j ) <= N; ++ j ) {
        for( int i = 1; i + ( 1 << j ) - 1 <= N; ++ i ) {
            st[i][j] = max( st[i][j - 1], st[i + ( 1 << ( j - 1 ) )][j - 1] );
        }
    }
}
int query( int l, int r ) {
    int k = lg2[r - l + 1];
    return max( st[l][k], st[r - ( 1 << k ) + 1][k] );
}
/* ======================================== */
} st;

map<int, int> mp;
int a[maxn];
int ys[maxn], rs[maxn];

void solve( ) {
    int n = read( );

    for( int i = 1; i <= n; ++ i ) {
        ys[i] = read( );
        rs[i] = read( );
    }
    st.init( n, rs );

    int q = read( );
    for( int i = 1; i <= q; ++ i ) {
        int Y = read( ), X = read( );
        int py = lower_bound( ys + 1, ys + n + 1, Y ) - ys;
        int px = lower_bound( ys + 1, ys + n + 1, X ) - ys;

        int l = upper_bound( ys + 1, ys + n + 1, Y ) - ys;
        int r = lower_bound( ys + 1, ys + n + 1, X ) - ys - 1;

        int mx = 0;
        if( l <= r ) mx = st.query( l, r );

        bool hasY = 0, hasX = 0;
        if( py <= n && ys[py] == Y ) hasY = 1;
        if( px <= n && ys[px] == X ) hasX = 1;

        if( hasY && hasX && rs[py] < rs[px] ) {
            cout << "false" << '\n';
            continue;
        } 
        if( hasX && mx >= rs[px] ) {
            cout << "false" << '\n';
            continue;
        }
        if( hasY && mx >= rs[py] ) {
            cout << "false" << '\n';
            continue;
        }

        if( hasY && hasX && px - py == X - Y ) {
            cout << "true" << '\n';
        } else {
            cout << "maybe" << '\n';
        }
    }
}

记录

• 新增：三值判定应先寻找已知信息中的矛盾，再判断信息是否完整；未知端点也可能因为可选值区间为空而直接判假。

• 分类：C