赛时想到的离谱 606060 分做法:
O(mn)O(mn)O(mn) 求检测到第 iii 辆车通过第 jjj 个测速仪时是否超速;
然后得到这样一串东西:
000110 011100 111000 001110 111110 000000
删除带有包含关系的区间以及全 000 行和全 000 列,并按左端点排序:
00011 01110 11100
右转 909090 度:
100 110 110 011 001
然后就成了一个线段覆盖问题
所以这个思路怎么优化成 O(nlogn)O(nlogn)O(nlogn)?