P11186 题解

· · 题解

题意回顾

给定三目运算表达式，其中无括号且仅含有常数和比大小运算式，多次求值。

分析

因为表达式里面内容的值域不大，所以考虑开个桶子计算出每个可能的值对应的表达式值，如果参数值大于 10^5 则与参数值为 10^5+1 是等价的。

考虑使得运算进入某个分支的参数取值集合是一段连续的区间，因此只要在表达式树上找到每个结点的对应区间，即可给每个可能的参数值来赋值上一个表达式值。

如何加速表达式树找子结点的过程？考虑一个表达式区间（子表达式），其要么是一个常数，要么是 x?a?b:c 的形式，第一个 ? 表示大小于符号，b 或 c 都是子表达式。x?a 是很短的可以遍历，因此只需要找到每个 ? 对应的 : 的位置，即可在接近于常数的复杂度内分解一个子表达式。

我们设计递归函数 solve(l, r, vall, valr)，表示由字符 l 到字符 r 构成的子表达式在参数取值为 [vall,valr] 区间内时会被计算到，按照以上所述方法分类讨论表达式是否为常数以及对进行非常数表达式进行分解和参数取值区间的分解即可，复杂度为 O(n \log w) ， n,w 分别为三目运算符个数和表达式内所有值的值域范围。

注意静态数组要开 14n 而不是 n 。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int cnt = 0;
int n, m, q;
string str;
stack<int> sta;
vector<int> vec;
int sgn[N * 14];//?->:
int buc[N * 14];
inline int getnum(int l, int r) {
    int val = 0;
    for(int i = l; i <= r; i++) val = val * 10 + str[i] - '0';
    return val;
}
void solve(int l, int r, int vall, int valr) {
    if(vall > valr) return;
    if(str[l] != 'x') {
        int tps = getnum(l, r);
        for(int i = vall; i <= valr; i++) buc[i] = tps;
        return;
    }
    int pos = 0;
    for(int i = l; i <= r; i++) {
        if(str[i] == '?') {
            pos = i;
            break;
        }
    }
    int tps = getnum(l + 2, pos - 1);
    if(str[l + 1] == '<') solve(pos + 1, sgn[pos] - 1, vall, tps - 1), solve(sgn[pos] + 1, r, tps, valr);
    else solve(pos + 1, sgn[pos] - 1, tps + 1, valr), solve(sgn[pos] + 1, r, vall, tps);
}
int main() {
    scanf("%d%d", &m, &q);
    cin >> str;
    n = str.size();
    str = " " + str;
    for(int i = 1; i <= n; i++) {
        if(str[i] == '?') {
            sta.push(i);
        } else if(str[i] == ':') {
            sgn[sta.top()] = i;
            sta.pop();
        }
    }
    solve(1, n, 1, 1e5 + 1);
    int x;
    for(int i = 1; i <= q; i++) {
        scanf("%d", &x);
        if(x > 1e5) x = 1e5 + 1;
        printf("%d\n", buc[x]);
    }
    return 0;
}