我在写莫队对询问排序的时候,写成下面这样会只有两个数据点 AC,其余数据点全部 TLE。
lim=500;
for(int cx=0,u,v;cx<q;++cx){
std::cin>>u>>v;
qs[cx]=query_t{u,v,cx};
}
std::sort(qs,qs+q);
std::fill(md.big,md.big+hspp+1,1);
但是如果把 lim 的计算放在后面,如下:
for(int cx=0,u,v;cx<q;++cx){
std::cin>>u>>v;
qs[cx]=query_t{u,v,cx};
}
lim=500;
std::sort(qs,qs+q);
std::fill(md.big,md.big+hspp+1,1);
就只有两个数据点 TLE,其余全部 AC。请问这个是什么原理呢?
另外,我写的这份代码总是 TLE,交了三页还是 78 分,不知道是复杂度假了还是什么地方写错了,我打算写的是 O(n4V+nq+qlogq+logVq3V) 复杂度。
全代码见剪贴板。