题解：CF2157F Git Gud
elswzl
·
·
题解
令操作次数 M = 10^6, 则 1000=\sqrt{M}，N=\frac{M}{4}。后续会用这些分析次数。
1.5\times 10^6 做法
假设没有 +1000 的代价，那么很自然会想到从小到大枚举 y 并将 l 设为 1，次数 N。
进一步，看到 \sqrt{M}=1000 自然会联想到根号分块做法。我们不妨每 B 个数字分成一个块，然后对于每个块所代表的区间 [kB+1,(k+1)B]，让它们都变成 (k+1)B。这里，可以用类似前文所提到的操作，有一点不一样的是你要把从后往前的每一块一起做。这一步的操作次数是 N+B\sqrt{M}。这一步操作我们称之为“基本操作”。
此时，我们剩下了 B, 2B, \ldots, N 这 \frac{N}{B} 个数字。再用一次前文所提到的操作。这一步的操作次数是 N+\frac{N\sqrt{M}}{B}。我们称之为“最终操作”。
## $O($能过$)$ 做法
只分一次块根本过不了，那我们是否可以多次分块呢？
分块时先分成长度为 $K$ 的块执行一次基本操作，再把剩下的 $\frac{N}{K}$ 个数字分成长 $B$ 的块执行一次，最后执行一次最终操作。操作次数为 $N+K\sqrt{M}+N+B\sqrt{M}+N+\frac{N\sqrt{M}}{KB}$。
化一下式子，$3N+(B+K+\frac{N}{BK})\sqrt{M} \geq 3N+3\sqrt[3]{N}\sqrt{M}$ 当且仅当 $B=K=\sqrt[3]{N}$。可以通过此题。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,B;
basic_string<pair<int,int> >ans;
void out(){
cout<<ans.size()<<"\n";
for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<"\n";
exit(0);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
B=pow(n,0.333333333333);
for(int i=1;i<B;i++){
basic_string<pair<int,int> >t;
for(int j=i;j<=n;j+=B)t+={j,1};
if(t.size()){
for(int i=t.size()-1;i>=0;i--)ans+=t[i];
}
}
n/=B;
if(n==0)out();
for(int i=1;i<B;i++){
basic_string<pair<int,int> >t;
for(int j=i;j<=n;j+=B)t+={j*B,B};
if(t.size()){
for(int i=t.size()-1;i>=0;i--)ans+=t[i];
}
}
for(int i=B;i<=n;i+=B)ans+={i*B,B*B};
out();
return 0;
}
```