RT，第四个大样例用了55s，但这玩意我怎么算都是O（n）

#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;

stack<char> sym;
stack<int> tmp;
int ans_and,ans_or;
int len;
char s[1000005];
char sz[1000005];
int nxt1[1000005],nxt2[1000005];

inline void change()
{
	for(int i=0;i<strlen(s);++i)
	{
		if(s[i]=='0' || s[i]=='1')
			sz[++len]=s[i];
		else
		{
			if(s[i]=='&')
			{
				while(!sym.empty() && sym.top()=='&')
				{
					sz[++len]='&';
					sym.pop();
				}
				sym.push('&');
			}
			else if(s[i]=='|')
			{
				while(!sym.empty() && sym.top()!='(')
				{
					sz[++len]=sym.top();
					sym.pop();
				}
				sym.push('|');
			}
			else if(s[i]=='(')
				sym.push('(');
			else
			{
				while(!sym.empty() && sym.top()!='(')
				{
					sz[++len]=sym.top();
					sym.pop();
				}
				sym.pop();
			}		
		}
	}
	while(!sym.empty())
	{
		sz[++len]=sym.top();
		sym.pop();
	}
}
inline void build()
{
	for(int i=1;i<=len;++i)
	{
		if(sz[i]=='0' || sz[i]=='1')
			tmp.push(i);
		else
		{
			int p1=tmp.top();
			tmp.pop();
			int p2=tmp.top();
			tmp.pop();
			nxt1[i]=p2,nxt2[i]=p1;
			tmp.push(i);
		}
	}
}
inline int dfs(int x)
{
	if(sz[x]=='0' || sz[x]=='1') 
		return sz[x]-'0';
	int l=dfs(nxt1[x]);
	if(sz[x]=='&' && l==0)
	{
	//	printf("ans_and++:in %d\n",x);
		ans_and++;
		return 0;
	}
	else if(sz[x]=='|' && l==1)
	{
	//	printf("ans_or++:in %d\n",x);
		ans_or++;
		return 1;
	}
	int r=dfs(nxt2[x]);
	return r;	
} 
int main()
{
	freopen("expr4.in","r",stdin);
	freopen("expr.out","w",stdout);
	scanf("%s",s);
	change();
	printf("!!!");
	build();
	printf("%d\n",dfs(len));
	printf("%d %d",ans_and,ans_or);
	return 0;
}