申请加强数据
查看原帖
申请加强数据
518899
FXT1110011010OI楼主2024/3/23 14:56

这篇题解 以及 这篇题解 中的分块做法似乎可以通过特殊数据构造卡掉。

把所有的点放在同一行,例如坐标分别为 (1,1),(1,2),(1,3),…,(1,n)(1, 1), (1, 2), (1, 3), \dots , (1, n),每次查询左上角 (1,1)(1, 1) 右下角 (1,n)(1, n) 的矩形。因为没有“中间块”的存在,每次询问的时间会被卡到 O(n)O(n),所有询问就是 O(mn)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

2024/3/23 14:56
加载中...