@[DengDuck](/user/501947)
这样是n log^2 n的
```cpp
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-(x))
void getmn(long long x,long long y)
{
while(x<=y)
{
cerr<<(bitset<20>(x))<<" "<<(bitset<20>(y))<<endl;
if(y-lowbit(y)+1<x)
{
y--;
}
else
{
y-=lowbit(y);
}
}
}
int main(){
getmn(2,(1<<19)-1);
return 0;
}
```
by konyakest @ 2022-12-05 09:38:07
@[konyakest](/user/482660) 求详细解释
by DengDuck @ 2022-12-05 09:40:06
我觉得这是单log欸qwq 同求解释
by DitaMirika @ 2022-12-05 09:46:51
@[DengDuck](/user/501947) @[SweetOrangeOvO](/user/236862) 自己运行我发的那个程序,得到y的输出(二进制形式)为
```cpp
01111111111111111111
01111111111111111110
01111111111111111100
01111111111111111000
01111111111111110000
01111111111111100000
01111111111111000000
01111111111110000000
01111111111100000000
01111111111000000000
01111111110000000000
01111111100000000000
01111111000000000000
01111110000000000000
01111100000000000000
01111000000000000000
01110000000000000000
01100000000000000000
01000000000000000000
00111111111111111111
00111111111111111110
00111111111111111100
00111111111111111000
00111111111111110000
00111111111111100000
00111111111111000000
00111111111110000000
00111111111100000000
00111111111000000000
00111111110000000000
00111111100000000000
00111111000000000000
00111110000000000000
00111100000000000000
00111000000000000000
00110000000000000000
00100000000000000000
00011111111111111111
00011111111111111110
00011111111111111100
00011111111111111000
00011111111111110000
00011111111111100000
00011111111111000000
00011111111110000000
00011111111100000000
00011111111000000000
00011111110000000000
00011111100000000000
00011111000000000000
00011110000000000000
00011100000000000000
00011000000000000000
00010000000000000000
00001111111111111111
00001111111111111110
00001111111111111100
00001111111111111000
00001111111111110000
00001111111111100000
00001111111111000000
00001111111110000000
00001111111100000000
00001111111000000000
00001111110000000000
00001111100000000000
00001111000000000000
00001110000000000000
00001100000000000000
00001000000000000000
00000111111111111111
00000111111111111110
00000111111111111100
00000111111111111000
00000111111111110000
00000111111111100000
00000111111111000000
00000111111110000000
00000111111100000000
00000111111000000000
00000111110000000000
00000111100000000000
00000111000000000000
00000110000000000000
00000100000000000000
00000011111111111111
00000011111111111110
00000011111111111100
00000011111111111000
00000011111111110000
00000011111111100000
00000011111111000000
00000011111110000000
00000011111100000000
00000011111000000000
00000011110000000000
00000011100000000000
00000011000000000000
00000010000000000000
00000001111111111111
00000001111111111110
00000001111111111100
00000001111111111000
00000001111111110000
00000001111111100000
00000001111111000000
00000001111110000000
00000001111100000000
00000001111000000000
00000001110000000000
00000001100000000000
00000001000000000000
00000000111111111111
00000000111111111110
00000000111111111100
00000000111111111000
00000000111111110000
00000000111111100000
00000000111111000000
00000000111110000000
00000000111100000000
00000000111000000000
00000000110000000000
00000000100000000000
00000000011111111111
00000000011111111110
00000000011111111100
00000000011111111000
00000000011111110000
00000000011111100000
00000000011111000000
00000000011110000000
00000000011100000000
00000000011000000000
00000000010000000000
00000000001111111111
00000000001111111110
00000000001111111100
00000000001111111000
00000000001111110000
00000000001111100000
00000000001111000000
00000000001110000000
00000000001100000000
00000000001000000000
00000000000111111111
00000000000111111110
00000000000111111100
00000000000111111000
00000000000111110000
00000000000111100000
00000000000111000000
00000000000110000000
00000000000100000000
00000000000011111111
00000000000011111110
00000000000011111100
00000000000011111000
00000000000011110000
00000000000011100000
00000000000011000000
00000000000010000000
00000000000001111111
00000000000001111110
00000000000001111100
00000000000001111000
00000000000001110000
00000000000001100000
00000000000001000000
00000000000000111111
00000000000000111110
00000000000000111100
00000000000000111000
00000000000000110000
00000000000000100000
00000000000000011111
00000000000000011110
00000000000000011100
00000000000000011000
00000000000000010000
00000000000000001111
00000000000000001110
00000000000000001100
00000000000000001000
00000000000000000111
00000000000000000110
00000000000000000100
00000000000000000011
00000000000000000010
```
时间复杂度是 $O(\log n+(\log n-1)+(\log n-2)+...+1)=O(\log^2 n)$
~~我没看题,如果这种情况不可能出现,就当我没说~~
by konyakest @ 2022-12-05 10:47:09
@[konyakest](/user/482660) 谢谢
by DengDuck @ 2022-12-05 10:48:35
@[DengDuck](/user/501947) 不过这种情况很罕见,平均情况还是 $O(\log n)$的,~~就怕毒瘤出题人卡~~
by konyakest @ 2022-12-05 10:50:31