36pts tle求调
查看原帖
36pts tle求调
959548
youwhenway_second楼主2024/10/13 19:51
#include<bits/stdc++.h>
using namespace std;
int m,q,x;
string s;
struct node{
	int l,r;
	int ls,rs,fa;
};
vector<node> t;
int toi(int l,int r){
	int re=0;
	for (int i=l;i<=r;i++)re=(re<<3)+(re<<1)+(s[i]^48);
	return re;
}
bool f(int i){
	int l=t[i].l,r=t[t[i].ls].l-2;
	char op=s[l+1];
	if (op=='<')return x<toi(l+2,r);
	return x>toi(l+2,r);
}
bool isn(int l,int r){
	for (int i=l;i<=r;i++)if ('0'>s[i]||s[i]>'9')return 0;
	return 1;
}

void build(int l,int r,int root){
	short op=0,wh=0,mh=0;
	int ll=l,lr=l,ml=r,mr=r,rl=r,rr=r;
	bool f=0;
	for (int i=l;i<=r;i++){
		if (s[i]=='?'&&!f)f=1,lr=i-1,op++,ml=i+1;
		if (s[i]=='?')wh++;
		else if (s[i]==':'){
			mh++;
			if (wh==mh){
				mr=i-1;
				op++;
				rl=i+1;
				break;
			}
		}
	}
	//cout<<ll<<' '<<lr<<' '<<ml<<' '<<mr<<' '<<rl<<' '<<rr<<'\n';
	int now=t.size();
	t.push_back({l,r,-1,-1,root});
	if (!isn(l,r)){
		t[now].ls=t.size();
		build(ml,mr,now);
		t[now].rs=t.size();
		build(rl,rr,now);
	}
	return;
}
void solve(){
	cin>>x;
	int now=0;
	while(t[now].ls!=-1){
		if (f(now))now=t[now].ls;
		else now=t[now].rs;
	}
	cout<<toi(t[now].l,t[now].r)<<'\n';
}
signed main(){
	//freopen("expr3.in","r",stdin);
	cin>>m>>q>>s;
	build(0,s.size()-1,-1);
//	for (int i=0;i<t.size();i++){
//		cout<<t[i].l<<' '<<t[i].r<<' ';
//		f(i);
//	}
	while(q--){
		solve();
	}
	return 0;
}
2024/10/13 19:51
加载中...