这篇题解 以及 这篇题解 中的分块做法似乎可以通过特殊数据构造卡掉。
把所有的点放在同一行,例如坐标分别为 (1,1),(1,2),(1,3),…,(1,n),每次查询左上角 (1,1) 右下角 (1,n) 的矩形。因为没有“中间块”的存在,每次询问的时间会被卡到 O(n),所有询问就是 O(mn),会 TLE。
造数据程序:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n = 1e5, m = 1e5;
cout << n << ' ' << m << endl;
for (int i = 1; i <= n; i ++ ) cout << 1 << ' ' << i << ' ' << 1 << endl;
while (m -- ) cout << "1 1 1 " << n << endl;
return 0;
}
本地实测分块过不去qwq