【题解】洛谷P11186： 三目运算

不好玩！！！

这是个树形结构，直接暴力模拟，但过不去，但是需要发现答案是个区间，我们对字符串处理时记录最大值最小值，然后到叶子节点时我们将此时的区间存起来，查询时直接二分查询这个数对于的区间就可以了。

总结：不好玩！！！

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;

int m,q;
string s;


struct ss{
	int x;
	int nxt[3];
	int flag;
	//nxt下一个数的位置
	//flag 1:> 2:< 3:结束 
}a[N];

int x=1;

struct sss{
	int l,r,val;
};

vector<sss> v;
int cnt=1;
void dfs(int cnt,int mi,int mx){
	
	if(s[x]=='x'){
		x++;
		if(s[x]=='>')
			a[cnt].flag=1;
		else
			a[cnt].flag=2;
		x++;
		
		int sum=0;
		while(s[x]>='0'&&s[x]<='9'){
			sum*=10;
			sum+=s[x]-'0';
			x++;
		}
		a[cnt].x=sum;
		x++;
			
		if(a[cnt].flag==1){
			dfs(cnt+1,sum+1,mx);
		}
		else{
			dfs(cnt+1,mi,sum-1);
		}
		if(a[cnt].flag==1){
			dfs(cnt+2,mi,sum);
		}
		else{
			dfs(cnt+2,sum,mx);
		}
	}
	else{
		int sum=0;
		while(s[x]>='0'&&s[x]<='9'){
			sum*=10;
			sum+=s[x]-'0';
			x++;
		}
		x++;
		if(mi<=mx){
			v.push_back({mi,mx,sum});
		}
	}
}

bool cmp(sss g,sss h){
	return g.l<h.l;
}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr); 
//	freopen("expr4.in","r",stdin);
//	freopen("std.out","w",stdout);
	
	cin>>m>>q;
	
	cin>>s;
	
	s='%'+s;
	
	dfs(1,1,10000000);
	
	sort(v.begin(),v.end(),cmp);
	
	while(q--){
		int x;
		cin>>x;	
		int l=0,r=v.size()-1,mid;
		while(l<r){
			mid=(l+r+1)>>1;
			if(v[mid].l<=x){
				l=mid;
			}
			else{
				r=mid-1;
			}
		}
		cout<<v[l].val<<"\n";
	}
    return 0;
}