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;
}