求助复杂度

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
struct node{
	int ls,rs;
	char op;
}T[N];
string s;
int tot=1;//节点个数 
int a[N];//每个右括号与之匹配的左括号的位置  
int lst[N];//&的上一个|
bool flagC=true;
void build(int p,int l,int r){
	if(l==r){
		T[p].ls=T[p].rs=0;
		T[p].op=s[l];
		return;
	}
	int cnt=0;//right-left 为0说明不在括号内 
	int pos=-1;//最后一个运算符的位置 
	int pos1=-1,pos2=-1;//the last of & |
	int i=r;
	while(i>=l){
		if(s[i]==')'){
			i=a[i]-1;
			continue;
		}
		if(s[i]=='&'||s[i]=='|'){
			if(s[i]=='&'&&pos1==-1){
				if(lst[i]<l){
					pos1=i;
					break;
				}
				else{
					if(flagC){
						pos2=lst[i];
						break;
					} 
					else if(pos1==-1) pos1=i;
				}
			}
			if(s[i]=='|'&&pos2==-1){
				pos2=i;
				break;
			}
		}
		i--;
	}
	if(pos2!=-1) pos=pos2;
	else pos=pos1;
	if(pos==-1) build(p,l+1,r-1);//(S)的情况
	else{
		T[p].op=s[pos];
		T[p].ls=++tot;
		build(tot,l,pos-1);
		T[p].rs=++tot;
		build(tot,pos+1,r);
	} 
}
int tot1,tot2;
int solve(int p){
	char op=T[p].op;
	int ls=T[p].ls,rs=T[p].rs;
	if(op=='0'||op=='1'){
		return op-'0';
	}
	if(op=='&'){
		int t1=solve(ls);
		if(t1==0){
			tot1++;
			return 0;
		}
		return solve(rs);
	}
	else{
		int t1=solve(ls);
		if(t1==1){
			tot2++;
			return 1;
		}
		return solve(rs);
	}
}

int main(){
	//freopen("expr4.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>s;
	int len=s.size(); 
	for(int i=0;i<len;i++){
		if(s[i]=='('||s[i]==')'){
			flagC=false;
			break;
		}
	}
	stack<int> st;
	for(int i=len-1;i>=0;i--){
		if(s[i]==')') st.push(i);
		if(s[i]=='('){
			a[st.top()]=i;
			st.pop();
		}
	}
	int now=-1;
	for(int i=0;i<len;i++){
		if(s[i]=='&'){
			lst[i]=now;
		}
		else if(s[i]=='|'){
			now=i;
		}
	}
	//for(int i=0;i<len;i++) cout<<a[i]<<' ';
	//cout<<'\n';
	build(1,0,len-1);
	/*
	for(int i=1;i<=tot;i++){
		cout<<T[i].op<<' '<<i<<' '<<T[i].ls<<' '<<T[i].rs<<'\n';
	}
	*/
	cout<<solve(1)<<'\n';
	cout<<tot1<<' '<<tot2<<'\n';
	
	return 0;
}