题目大意是给一串数 要支持两个操作,一是要把一个区间剪切到一个点后面,另一个是把这个区间的数反转。。
程序我写好了,可是悲剧的TLE了。。
然后我发现是在查找第x位的时候往标记下传了,改过后就ac了。。
我想问的是。。为什么不加标记下传会tle而不是wa。。?难道会进入死循环。。?
int Find(int X){
int Temp = Root;
Passdown(Temp);//之前没有这行
while(1){
if(X == T[T[Temp].left].size + 1) return Temp;
if(X <= T[T[Temp].left].size)
Temp = T[Temp].left;
else
X -= T[T[Temp].left].size+1, Temp = T[Temp].right
Passdown(Temp);//和这行
}
}
顺便发下我的标记下传是这么写的- -。。
void Passdown(int X){
if(T[X].rev){
int LTemp = T[X].left;
int Rtemp = T[X].right;
T[X].right = LTemp;
T[X].left = Rtemp;
T[T[X].left].rev ^= T[X].rev;
T[T[X].right].rev ^= T[X].rev;
T[X].rev = 0;
}
}
纠结了。。。
程序我写好了,可是悲剧的TLE了。。
然后我发现是在查找第x位的时候往标记下传了,改过后就ac了。。
我想问的是。。为什么不加标记下传会tle而不是wa。。?难道会进入死循环。。?
int Find(int X){
int Temp = Root;
Passdown(Temp);//之前没有这行
while(1){
if(X == T[T[Temp].left].size + 1) return Temp;
if(X <= T[T[Temp].left].size)
Temp = T[Temp].left;
else
X -= T[T[Temp].left].size+1, Temp = T[Temp].right
Passdown(Temp);//和这行
}
}
顺便发下我的标记下传是这么写的- -。。
void Passdown(int X){
if(T[X].rev){
int LTemp = T[X].left;
int Rtemp = T[X].right;
T[X].right = LTemp;
T[X].left = Rtemp;
T[T[X].left].rev ^= T[X].rev;
T[T[X].right].rev ^= T[X].rev;
T[X].rev = 0;
}
}
纠结了。。。