数据过水
查看原帖
数据过水
104379
Cesare楼主2021/10/24 11:41

二分找到第一个大于右端点的左端点后暴力往后找第一个没被标记的区间可以直接过

就像这样:

j = Find1(i, j, ed); 
for (; j <= m1; ++j) if (!T[j]) break;

卡的方法:构造一堆很大的区间:[1,n],[2,n1][3,n2]...[1, n], [2, n - 1] [3, n - 2]...

然后 [n+1,2n][n+2,2n1][n+3,2n2]...[n + 1, 2n] [n + 2, 2n - 1] [n + 3, 2n-2]...

可以卡成 O(n2)O(n^2)

跑得比 nlog2nnlog^2n 快我是没想到的

2021/10/24 11:41
加载中...