暴力建树re求调
查看原帖
暴力建树re求调
1082433
PhoenixWright楼主2024/10/13 12:23
#include<bits/stdc++.h>
using namespace std;
int m,q,x;
string s,tree[200010];
string sub(string s,int l,int r){
	string c;
	for(int i=l;i<=r;i++){
		c+=s[i];
	}
	return c;
}
void creat(string s,int id){
	if(s.find("?")>s.size()){
		tree[id]=s;
		return;
	}
	tree[id]=s.substr(0,s.find('?'));
	int i=1,ans=0,sn=0;
	while(i<s.size()){
		if(s[i]=='?')ans++;
		if(s[i]==':')sn++;
		if(sn==ans&&sn&&ans){
			break;	
		}
		i++;
	}
	creat(sub(s,s.find("?")+1,i-1),id*2);
	creat(sub(s,i+1,s.size()-1),id*2+1);
	
}
void dfs(int x,int id){
	if(tree[id].find("<")>tree[id].size()&&tree[id].find(">")>tree[id].size()){
		cout<<tree[id]<<endl;
		return;
	}
	long long p=tree[id].size();
	if(tree[id].find("<")<p){
		int q=tree[id].find("<")+1;
		int n=0;
		while(q<p){
			n=(n<<1)+(n<<3)+(tree[id][q]^48);
			q++;
		}
		if(x<n)dfs(x,id*2);
		else dfs(x,id*2+1);
	}else{
		int q=tree[id].find(">")+1;
		int n=0;
		while(q<p){
			n=(tree[id][q]^48)+(n<<1)+(n<<3);
			q++;
		}
		if(x>n)dfs(x,id*2);
		else dfs(x,id*2+1);
	}
	return;
}
int main(){
	cin>>m>>q;
	cin>>s;
	creat(s,1);
	while(q--){
		cin>>x;
		dfs(x,1);
	}
	return 0;
}
2024/10/13 12:23
加载中...