[甚至还吊打了线段树+位运算快读](https://www.luogu.com.cn/discuss/523702)
by rui_er @ 2023-01-06 22:32:47
和 @[rui_er](/user/122461) 贴贴
by Astra0 @ 2023-01-06 22:36:49
[提交记录](https://www.luogu.com.cn/record/98870093)
by rui_er @ 2023-01-06 22:41:20
这个运算量好像也就不到 2e8,感觉卡掉不太容易
吊打线段树不太现实,随便写的线段树最慢[343ms](https://www.luogu.com.cn/record/98871687) ~~刚好一半~~
by 云浅知处 @ 2023-01-06 22:42:20
感觉只放 st 表不如把 $n$ 开到 1e6 然后把 $m$ 开到 5e6 或者 1e7,给个种子自己生成输入()
by 云浅知处 @ 2023-01-06 22:43:52
@[rui_er](/user/122461) 构造了一组数据在我本地卡到了 6s
```cpp
#include<bits/stdc++.h>
using namespace std;
int randint(int l,int r){return rand()*rand()%(r-l+1)+l;}
signed main(void){
int N=1e5,M=2e6;
cout<<N<<" "<<M<<endl;
for(int i=1;i<=N;i++)cout<<randint(0,1e9)<<" ";puts("");
int S=(int)(sqrt(N)),cnt=0;
for(int i=1;i<=N;i+=S){
for(int j=N;j>=i;j-=S)cnt++,cout<<i<<" "<<j<<'\n';
}
for(int i=1;i<=M-cnt;i++){
int l=randint(1,N),r=randint(1,N);
if(l>r)swap(l,r);
cout<<l<<" "<<r<<'\n';
}
return 0;
}
```
by 云浅知处 @ 2023-01-06 22:49:42
@[云浅知处](/user/307453) orz
by rui_er @ 2023-01-06 22:55:33
@[rui_er](/user/122461) 太假了/kk
by 云浅知处 @ 2023-01-07 01:01:25