当我写 char s[MAXN]，MAXN = 1e5*20 时，跑得巨慢。

提交记录：this。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 * 20;
const int MAXN2 = 1e5 + 5;
unordered_map <int,int> pos;//记录每个 ? 对应的 :
char s[MAXN];
int ans[MAXN2];
inline int in(){
	int k=0;
	char a=getchar();
	while(a<'0'||a>'9') a=getchar();
	while(a>='0'&&a<='9') k=k*10+a-'0',a=getchar();
	return k;
}
void out(int x){
	if(x>=10) out(x/10);
	putchar(x%10+'0');
}
stack <int> st;
void setup(int l,int r,pair<int,int> f){
	if(s[l]!='x'){
		// 在 f.fisrt ~ f.second 范围内的树都是 x 为答案 
		int x = 0;
		while(s[l]>='0'&&s[l]<='9') x=x*10+s[l]-'0',l++;
		for(int i=f.first;i<=f.second;i++) ans[i] = x;
		return;
	}
	int ll = l+2;
	int x = 0;
	while(s[ll]>='0'&&s[ll]<='9') x=x*10+s[ll]-'0',ll++;
//	cout << ll << endl;
	if(s[l+1]=='>'){
//		cout << pos[ll]-1 << endl;
		setup(ll+1,pos[ll]-1,make_pair(x+1,f.second));
		setup(pos[ll]+1,r,make_pair(f.first,x));
	}else{
		setup(ll+1,pos[ll]-1,make_pair(f.first,x-1));
		setup(pos[ll]+1,r,make_pair(x,f.second));
	}
}
signed main(){
	int m=in(),q=in();
	scanf("%s",s+1);
//	cout << strlen(s+1) << endl;
	for(int i=1;i<=strlen(s+1);i++){
		if(s[i]=='?') st.push(i);
		else if(s[i]==':'){
			int tot = st.top();
			pos[tot] = i;
			st.pop();
		}
	}
	setup(1,strlen(s+1),make_pair(1,m+1));
	while(q--){
		int x = in();
//		cout << "ans = " ;
		if(x<=m) printf("%lld",ans[x]);
		else printf("%lld",ans[m+1]);
		putchar('\n');
	}
	
	return 0;
}

而我用 cin 读，却没有关闭同步流的时候情况下交了：this。

跑得飞快

Code

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN2 = 1e5 + 5;
unordered_map <int,int> pos;//记录每个 ? 对应的 :
string s;
int ans[MAXN2];
inline int in(){
	int k=0;
	char a=getchar();
	while(a<'0'||a>'9') a=getchar();
	while(a>='0'&&a<='9') k=k*10+a-'0',a=getchar();
	return k;
}
void out(int x){
	if(x>=10) out(x/10);
	putchar(x%10+'0');
}
stack <int> st;
void setup(int l,int r,pair<int,int> f){
	if(s[l]!='x'){
		// 在 f.fisrt ~ f.second 范围内的树都是 x 为答案 
		int x = 0;
		while(s[l]>='0'&&s[l]<='9') x=x*10+s[l]-'0',l++;
		for(int i=f.first;i<=f.second;i++) ans[i] = x;
		return;
	}
	int ll = l+2;
	int x = 0;
	while(s[ll]>='0'&&s[ll]<='9') x=x*10+s[ll]-'0',ll++;
//	cout << ll << endl;
	if(s[l+1]=='>'){
//		cout << pos[ll]-1 << endl;
		setup(ll+1,pos[ll]-1,make_pair(x+1,f.second));
		setup(pos[ll]+1,r,make_pair(f.first,x));
	}else{
		setup(ll+1,pos[ll]-1,make_pair(f.first,x-1));
		setup(pos[ll]+1,r,make_pair(x,f.second));
	}
}
signed main(){
	int m=in(),q=in();
	cin >> s;
	int n = s.size();
//	cout << strlen(s+1) << endl;
	for(int i=0;i<n;i++){
		if(s[i]=='?') st.push(i);
		else if(s[i]==':'){
			int tot = st.top();
			pos[tot] = i;
			st.pop();
		}
	}
	setup(0,n-1,make_pair(1,m+1));
	while(q--){
		int x = in();
//		cout << "ans = " ;
		if(x<=m) printf("%lld",ans[x]);
		else printf("%lld",ans[m+1]);
		putchar('\n');
	}
	
	return 0;
}

求解释。