记录

wa on #3 #4

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int m,q;
string s;
struct Node
{
	string s;
	bool flag;
	int id;
};
Node val[N];
int ch[N][2];
int ans[N];
stack<Node> st;
int fa[N]; 
int tot=0;
struct node
{
	int num;
	int op=0;
}v[N];
void dfs(int o,int l,int r)
{
	if(v[o].op==0) 
	{
		for(int i=l;i<=r;i++)ans[i]=v[o].num;
		return;
	}
    else if(v[o].op==1)//大于 
    {
    	dfs(ch[o][0],v[o].num+1,r);
    	dfs(ch[o][1],l,v[o].num);
	}
	else//小于 
	{
		dfs(ch[o][0],l,v[o].num-1);
		dfs(ch[o][1],v[o].num,r);
	}
}
int main()
{
	cin>>m>>q;
	cin>>s;
	string now;
	bool flag=false; 
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='?')
		{
			tot++;
			val[tot]={now,flag,tot};
			st.push(val[tot]);
			now="";
			flag=0;
			if(val[tot].flag==1&&st.size()>=3){
				Node t1=st.top();
				st.pop();
				Node t2=st.top();
				st.pop();
				Node t3=st.top();
				st.pop();
				st.push(t1);
				ch[t3.id][t1.flag]=t1.id;
				fa[t1.id]=t3.id;
			}
			else if(val[tot].flag==0&&st.size()>=2)
			{
				Node t=st.top();
				st.pop();
				Node t2=st.top();
				st.push(t);
				ch[t2.id][t.flag]=t.id;
				fa[t.id]=t2.id; 
			}
		}
		else if(s[i]==':')
		{
			tot++;
			val[tot]={now,flag,tot};
			st.push(val[tot]);
			now="";
			flag=1;
			if(val[tot].flag==1&&st.size()>=3){
				Node t1=st.top();
				st.pop();
				Node t2=st.top();
				st.pop();
				Node t3=st.top();
				st.pop();
				st.push(t1);
				ch[t3.id][t1.flag]=t1.id;
				fa[t1.id]=t3.id;
			}
			else if(val[tot].flag==0&&st.size()>=2)
			{
				Node t=st.top();
				st.pop();
				Node t2=st.top();
				st.push(t);
				ch[t2.id][t.flag]=t.id;
				fa[t.id]=t2.id; 
			}
		}
		else
		{
			now=now+s[i];
		}
	}
	++tot;
	val[tot]={now,1,tot};
	ch[tot-2][1]=tot;
	fa[tot]=tot-2;
	for(int i=1;i<=tot;i++)
	{
		int sum=0;
		for(int j=0;j<val[i].s.size();j++)
		{
			int c=val[i].s[j];
			if('0'<=c&&c<='9')
			{
				sum=sum*10+c-'0'; 
			}
			if(c=='>')
			{
				v[i].op=1;
			}
			if(c=='<') 
			{
				v[i].op=-1;
			}
		}
		v[i].num=sum;
	 }
	dfs(1,1,m);
	while(q--)
	{
	  int x;
	  cin>>x;
	  if(x>m)x=m;
	  cout<<ans[x]<<endl;
	 }
	return 0;
}