题解：P11186 三目运算

我们将每个三目运算符抽象成二叉树上的一个点。然后令其左儿子为「数值1」，右儿子为「数值2」。特别的，若这两个儿子是十进制数，则单独为这样的十进制数做编号。

不难发现，这样建出的二叉树的叶子节点一定都是十进制数。

我们在这颗树上进行 dfs。在从根往叶子递归的过程中，维护 $L, R$ 表示只有当 $L < x < R$ 时程序才会进行到这个树点。特别的，若 $R - L \le 2$ 则停止递归。

这样当访问到叶子时，我们就能得知：若 $L < x < R$，那么整个分段常数表达式的值就是这个叶子所代表的十进制数。

代码比较丑陋：

```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e6 + 10, INF = 1e9;

int n, q;
char s[N];
int cnt;		// 树上的节点数量
int id[N];		// 如果这个位置是 ?/x/</>，给它标号。: 需要用栈处理。
int True[N], False[N];		// 第 i 个分段常数表达式，如果成立会执行哪个，如果不成立会执行哪个
int num[N];		// 如果 i 往后是一个十进制常数，先把它的值求出来
int than[N];		// 第 i 个表达式合法，必须大于 than[i] 或小于 -than[i]
pair<int, int> res[N];
int sz;

inline
void dfs(const int u, const int L, const int R) {		// 能进入这个点需要满足 > L 且 < R
	if (L + 1 > R - 1) return;
	if (!True[u] && !False[u]) {
		// 叶节点
		res[ ++ sz] = {L + 1, num[u]};
		return;
	}
	if (than[u] > 0) {
		if (True[u]) dfs(True[u], max(L, than[u]), R);
		if (False[u]) dfs(False[u], L, min(R, than[u] + 1));
	} else {
		if (True[u]) dfs(True[u], L, min(R, -than[u]));
		if (False[u]) dfs(False[u], max(L, -than[u] - 1), R);
	}
}

signed main() {
	scanf("%d%d%s", &n, &q, s + 1);
	int m = n;
	n = strlen(s + 1);
	
	bool flg = false;
	for (int i = 1; i <= n; ++ i ) flg |= s[i] == '?';
	
	if (!flg) {
		int x = 0;
		for (int i = 1; i <= n; ++ i )
			x = x * 10 + s[i] - '0';
		while (q -- ) cout << x << '\n';
		return 0;
	}
	
	stack<int> stk;
	for (int i = 1; i <= n; ++ i ) {
		if (s[i] == 'x') {
			cnt ++ ;
			id[i] = cnt;
		} else if (s[i] == '?' || s[i] == '<' || s[i] == '>') {
			id[i] = cnt;
		}
		
		if (s[i] == '?') stk.push(cnt);
		if (s[i] == ':') {
			id[i] = stk.top();
			stk.pop();
		}
	}
	
	for (int i = 1; i <= n; ++ i )
		if ((s[i - 1] == '?' || s[i - 1] == ':') && isdigit(s[i])) {
			int x = 0;
			for (int j = i; j <= n && isdigit(s[j]); ++ j ) {
				x = x * 10 + s[j] - '0';
			}
			id[i] = ++ cnt;
			num[id[i]] = x;
		}
	
	for (int i = 1; i <= n; ++ i ) {
		if (s[i] == '?') {
			True[id[i]] = id[i + 1];
		} else if (s[i] == ':') {
			False[id[i]] = id[i + 1];
		}
	}
	
	for (int i = 1; i <= n; ++ i )
		if (s[i - 1] == '>' || s[i - 1] == '<') {
			int x = 0;
			for (int j = i; j <= n && isdigit(s[j]); ++ j ) {
				x = x * 10 + s[j] - '0';
			}
			than[id[i - 1]] = s[i - 1] == '>' ? x : -x;
		}
	
	dfs(1, 0, INF + 1);
	
	sort(res + 1, res + sz + 1);
	
	while (q -- ) {
		int x;
		cin >> x;
		int lo = 1, hi = sz, ans;
		while (lo <= hi) {
			int mid = lo + hi >> 1;
			if (res[mid].first <= x) {
				ans = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
		cout << res[ans].second << '\n';
	}
	
	return 0;
}
```

正在渲染内容...