站外题RE求助
查看原帖
站外题RE求助
222578
jingkongwanglimiaoa楼主2023/8/24 23:19

rt,这是一份有个别点RE的代码

并且在C++98/C++11上都能过

C++14/C++14(O2)过不了

目前已经自查:

  • upper_bound之后附带变量nw的表达式没有越界(不会小于0或者大于vector长度)

  • 数组空间大概率没问题 开大两倍还是如此

不一定是越界 求助还有什么特别的RE问题吗(尤其是那种C++14新特性导致的问题)

# include <cstdio>
# include <vector>
# include <algorithm>
# include <iostream>
# define INF 0x3f3f3f3f3f3f3f3f
# define int long long
using namespace std;
const int N = 1e5+10;
int n,T,lk[N],ize[N],hp,hd,rt,fd[N],tre[N << (int)2],a[N],dfn[N];
vector<int> dd[N];
char op[3];
struct sth{
	int ue,we;
}e[N];
void dfs(int nw){
	hd++; dfn[nw] = hd; fd[hd] = nw; ize[nw] = 1;
	for (int i = lk[nw]; i; i = e[i].we){
		dfs(e[i].ue); ize[nw] += ize[e[i].ue]; 
		dd[nw].push_back(dfn[e[i].ue]);
	}
	dd[nw].push_back(dfn[nw]+ize[nw]); 
	return ;
}
void ad(int u,int v){
	e[++hp] = {v,lk[u]};
	lk[u] = hp;
}
void bui(int k,int l,int r){
	if (l == r){
		tre[k] = a[fd[l]];
		return ;
	}
	int mid = (l+r) >> 1;
	bui(k*2,l,mid); bui(k*2+1,mid+1,r);
	tre[k] = min(tre[k*2],tre[k*2+1]);
}
void upd(int k,int l,int r,int x,int val){
	if (x < l || x > r) return ;
	if (l==r){
		tre[k] = val;
		return ;
	}
	int mid = l+r >> 1;
	upd(k*2,l,mid,x,val);
	upd(k*2+1,mid+1,r,x,val);
	tre[k] = min(tre[k*2],tre[k*2+1]);
}
int que(int k,int l,int r,int L,int R){
	if (R < l || L > r) return INF;
	if (L <= l && R >= r){
		return tre[k];
	}
	int mid = l+r >> 1;
	return min(que(k*2,l,mid,L,R),que(k*2+1,mid+1,r,L,R));
}
signed main(){
	scanf("%lld %lld",&n,&T);
	int x,y;
	for (int i = 1; i <= n; i++){
		scanf("%lld %lld",&x,&a[i]);
		if (x) ad(x,i);
	}
	dfs(1); bui(1,1,n); rt = 1;
	while (T--){
		scanf("%s",op+1);
		if (op[1] == 'V'){
			scanf("%lld %lld",&x,&y); x = dfn[x];
			upd(1,1,n,x,y);
		}
		else if (op[1] == 'E'){
			scanf("%lld",&x); rt = x;
		}
		else{
			scanf("%lld",&x);
			if (rt == x) printf("%lld\n",que(1,1,n,1,n));
			else if (dfn[rt] > dfn[x] && dfn[rt] < dfn[x]+ize[x]){
				int nw = upper_bound(dd[x].begin(),dd[x].end(),	dfn[rt])-dd[x].begin();
				nw--;
				printf("%lld\n",min(que(1,1,n,1,dd[x][nw]-1),que(1,1,n,dd[x][nw+1],n)));	
			}
			else{
				printf("%lld\n",que(1,1,n,dfn[x],dfn[x]+ize[x]-1));
			}
		}
	}
	return 0;
}
2023/8/24 23:19
加载中...