8分re,暴力建树求调
查看原帖
8分re,暴力建树求调
1019115
duanxinyu2011楼主2024/10/13 18:12
#include<bits/stdc++.h>
using namespace std;
int m,q;
string s;
struct node 
{
	int x=0;
	char f;
}a[400005];
int tree(int k,int jie)
{
	int j=k;
	while(s[j]!='?'&&s[j]!=':')
	{
		if(s[j]=='x')
		{
			a[jie].f=s[j+1];
			int i=j+2,sum=0;
			while(s[i]>='0'&&s[i]<='9')
			{
				sum=sum*10+(s[i]-'0');
				i++;
			}
			a[jie].x=sum;
			j=i-1;
		}
		else if(s[j]>='0'&&s[j]<='9')
		{
			int i=j,sum=0;
			while(s[i]>='0'&&s[i]<='9')
			{
				sum=sum*10+(s[i]-'0');
				i++;
			}
			a[jie].f='*';
			a[jie].x=sum;
			j=i-1;
		}
		j++;
	}
	if(s[j]=='?')
	{
		int x=tree(j+1,2*jie);
		if(s[x]==':')
		{
			x=tree(x+1,2*jie+1);
		}
		j=x;
	}
	return j;
}
int main()
{
	cin>>m>>q;
	cin>>s;
	s+=":";
	int y=tree(0,1);
	for(int i=1;i<=q;i++)
	{
		int x,t=1;
		cin>>x;
		while(1)
		{
			if(a[t].f=='<'){
				if(x<a[t].x){
					t=t*2;
				}else{
					t=t*2+1;
				}
			}else if(a[t].f=='>'){
				if(x>a[t].x){
					t=t*2;
				}else{
					t=t*2+1;
				}
			}else if(a[t].f=='*'){
				cout<<a[t].x<<endl;
				break;
			}
		}
	}
	return 0;
}
2024/10/13 18:12
加载中...