警示后人 70 ~ 80 MLE / 2 TLE 整体二分

在整体二分过程中，将询问分成两部分时，应使用数组节省空间，而不是 vector。

CPP

q1[cnt1++] = q[i];
//q1.push_back(q[i]);
q2[cnt2++] = q[i];
//q2.push_back(q[i]);

并且，cnt1 和 cnt2 应在函数内定义。否则，当往下递归时会被改变。

CPP


Work(ql, ql + cnt1 - 1, vl, mid);//第一次
//若 cnt1 和 cnt2 为全局变量，则 此时 cnt1 和 cnt2 已经被改变，于是第二次时使用的 cnt1 已经不再是原来的 cnt1
Work(ql + cnt1, qr, mid + 1, vr);//第二次

应使用

CPP

void Solve() {
  ...
  int cnt1 = 0, cnt2 = 0;
  ...
}

警示后人 70 ~ 80 MLE / 2 TLE 整体二分

讨论操作

回复

相关推荐

警示后人 70 ~ 80 MLE / 2 TLE 整体二分